Boy, explaining this brings back memories; picalc48 is about two years old Okay, on to the math. If you have an enormous number, you can store the digits two at a time in strings or four at a time in short integers. Neither really conserves more space than the other, but to do arithmetic with strings in qb you first have to convert them to numbers using VAL(), and that takes time. Addition--------------------------------------------------------------- To add or subtract enormous numbers, as you probably know, is easy: just loop through and add corresponding array elements together, as if you were doing conventional arithmetic. Then there is the small matter of "carrying the one" (or whatever). If you did addition by hand, 12 + 19 ---- 31 where you implicitly carry the one. However, 31 = 3*10 + 1*1 = 2*10 + 11*1; so as long as you mentally keep a "divider" between the two digits you can just as easily say 12 + 19 ------ 2 11 where you just add the digits together while ignoring the carry. These two answers are *exactly the same*, except the second one didn't require all that costly checking to see if the first digit was > 10. It would save tons of time if adding two enormous numbers just looked like this: for i = 1 to number_of_words a(i) = a(i) + b(i) next i for several reasons: first, it doesn't matter whether you add the arrays together looping forwards or backwards; second, especially if you add many numbers together, not checking for overflow speeds things up a lot. The only caveat is that the numbers you store need lots of extra space, because the digits generated can get large (if I add 100 enormous numbers together and never carry the one, each array element needs at least two extra digits worth of space because all the array values will grow). This is why picalc48 uses long integers but with only four digits each; the extra space in each long means you'd have to add over a million numbers together to hit overflow, many more than will probably happen (DOS only gives you 64k of space anyway, and there's no conceivable reason to add up a million terms of an arctan series if only the first 100k will count towards digits of pi). Then you release all the carries at once, at the end! Here you work back- wards through the array, and for each element you chop off everything bigger than four digits long, then add it to the array element in front: for i = number_of_words to 2 step -1 quotient = a(i) \ 10000 a(i) = a(i) mod 10000 a(i-1) = a(i-1) + quotient next i Subtraction--------------------------------------------------------------- All the same rules apply to subtraction as do addition, as long as you replace "carry" with "borrow". So you should have no qualms about seeing 22 - 19 ------ 1 -7 After all, it's what you do implicitly in your head. You *could* test for digits < 0, add 10 to them and subtract one from the digit in front, but why? If you don't care what intermediate results look like the above form is just as meaningful and more quickly computed to boot. In practice, arctangent series involve alternately adding and subtracting big numbers, so the very big array elements you'd ordinarily generate by adding lots of numbers together will often be cancelled out by the very small negative numbers generated by subtracting lots of numbers. Also, there's a subtlety in "releasing borrows" after a long calculation, namely that dividing by 10000 yields a negative number, but one that's slightly too small (it's because of the way computers handle / and mod). See the code for tips on fixing it. Division by Small Numbers ------------------------------------------------ One of the nice things about arctangents is that in order to compute pi using them, this last section is all you need! Imagine in your mind's eye how you'd divide 3.2 by 7. You first write it out like this: _______ 7 | 3.2000 To perform the division, you bring down the 3: _______ 7 | 3.2000 3 then try and divide 3 by 7, which is 0 remainder 3: 0 _______ 7 | 3.2000 3 -0 --- 3 Now bring down the next digit: 0 _______ 7 | 3.2000 3 -0 --- 32 and try to divide 32 by 7, getting 4 remainder 4 04 _______ 7 | 3.0000 3 -0 --- 32 -28 --- 4 and now repeat for all the succeeding digits. The process is pretty easy: remainder = 0 for i = 1 to size_of_array dividend = remainder * 10 + array(i) 'bring down next digit array(i) = dividend \ denom 'make next digit of answer remainder = dividend mod denom 'set up for next digit next i Of course, the code I use does four digits at a time, so you see 10000 instead of 10. You also see lots of "&" notations in the code because it seems qb needs to make longs out of everything in the computations. It doesn't matter if remainder is negative, or more than one digit long; as long as dividend does not overflow the process is exactly the same. We'll see that in the specific case of arctangent formulas, however, this last will not crop up. Crunching Out Arctangents ------------------------------------------------ Enough with the math; let's crunch monster digits. It's desired to compute, for integers x, the arctangent of 1/x using 1 1 1 1 - - ----- + ----- - ----- + ..... x 3 x^3 5 x^5 7 x^7 to lots of precision. Well, you just saw how to compute 1/x to lots of digits, so that's no problem; but I hope you can see that beyond about 5 terms x becomes really big, so the long division process above won't work. This is easily fixed though: x^(huge number) may be huge, but it's only x^2 bigger than x^(huge number - 2). Thus if you know what 1/ x^53423 is, you can easuly find 1/ x^53425 by dividing that number by x^2, which is a constant after you decide which arctangent formula to use. Thus to carry out the computations you need two arrays, one to store the answer you build up piece by piece and the other to store 1/ x^(huge number) which you also build up by repeated division by x^2. Take a look at Machin's formula: pi = 16 * arctangent(1/5) - 4 * arctangent(1/239) You must add up two arctangents using the above process. Here's what the program does for the arctan(1/5) part, in pseudocode: 1. make two arrays, sum and term. Sum will hold the digits of the answer you build up and term holds powers of 1/x. Division never causes the digits involved to grow, so term can be an array of short integers, but if you're ignoring the carry until the end the array sum should be of long integers. 2. The fist term is 16/5, or 3.2; no computation is necessary, just make sum(1) = 3 and sum(2) = 2000 (four digits/term, remember?). the first power of 1/x is 1/5, or .2; thus term(1) = 0 and term(2) = 2000. Finally, let denom = 3. 3. Loop as long as you want: a. figure out whether the next term is added or subtracted into the array sum b. divide term array by 25 c. divide term array by denom and add/subtract it (whichever is appropriate) to the sum array. Note that you don't have to divide the *whole* term array and then add/subtract it; you can compute one digit, then use it, then another digit, then use that, etc. This saves you from needing a third array to hold a partial result that will be destroyed anyway. This is another very good reason for avoiding carrying of ones: if you handle the carry from addition, you have to work from the back of an array to the front, which means computing the whole division by denom, then adding it all on at once. Since memory space in qb is very limited, this allows many more digits to be computed. d. add 2 to denom That's it! The 1/239 term looks exactly the same, except intead of dividing by 5^2 = 25 ou must divide by 239^2 = 57121. That's as tough as things get. The fun in computing pi is not sorting out a terribly complicated algorithm, but in getting it to run *fast* Getting It to Run *Fast* -------------------------------------------------- [ ... to be continued when I have the time ...]