Decimal digits vs integer digits

[Valentin Albillo]

(02-22-2018 08:58 AM)pier4r Wrote:  Hmm ok so other question. Using your best routine for computing digits of Pi (and I know you developed some), giving 19 seconds on the same computer and same emu71, how many digits do you get. Still around 1700 or way more?

The original routine in the link I gave you was a quick, unoptimized job written on the fly specifically to get the 19729-digit result which was asked for in Take 5 with the minimum of fuss and the minimum of code. As such, it computes the exponentiation 2^65536 with a simple loop which performs 65536 multiprecision multiplications plus propagating the carries each time a multiplication is performed.

This is horribly inefficient but very simple to program so the part that does the multiprecision exponentiation is just 3 lines of code and, as I said, gets the 19729-digit result with minimum code complexity and I didn't care that it took 25 minutes to do the job. The correct way to do the exponentiation, which is much, much faster, is to use a bitmap scheme to substitute the 65536 multiplication by just 16 or so, which would get the result two or three orders of magnitude faster but would complicate somewhat the code, which for Take 5 wasn't required or desired.

The same applies to the particularization to compute your 345^678, so the 19 seconds are not representative of the difficulty, I can optimize the routine and reduce the 678 multiplications to 9 or 10 and thus reduce the time correspondingly to a second or two, but I won't do it because it's no use right now and there are better ways to prove the point, namely I've run some tests in the same old pc I mentioned and these are the results:

1) This is the 3-line program I've written to compute Pi in a multiprecision programming environment:

      1 input M% : M%-=1 : A=1 : B=1/sqrt(2) : S=1/4 : for N%=0 to M%
      2 T=A : A=(A+B)/2 : C=T-A : if N%<>M% then B=sqrt(T*B) : S-=2^N%*C*C
      3 next N% : print A*A/S

It implements an algorithm that performs a user-given number of iterations with quadratic convergence, i.e. the number of correct digits approximately doubles after each iteration. Let's check it:

      point 9
                  Words for fractionals 9 (Decimals for display 43)
      run
      ? 0
       4.0 (no correct digits but close)

      run
      ? 1
      2.9142135623730950488016887242096980785696715 (still none but closer)

      run
      ? 2
       3.1405792505221682483113312689758233117734397 (2 correct decimals)

      run
      ? 3
       3.1415926462135422821493444319826957743144363 (now 7)

      run
      ? 4
       3.1415926535897932382795127748018639743812242 (now 18)

      run
      ? 5
       3.1415926535897932384626433832795028841971132 (now 40)


As can be seen, each iteration approximately doubles the number of correct decimal places so let's go for something much bigger, say 1250+ decimals which will require as few as just 10 iterations:

         point 260
                Words for fractionals 260 (Decimals for display 1252)
      run
      ? 10

 3.14159265358979323846264338327950288419716939937510582097494459230781640628620
89986280348253421170679821480865132823066470938446095505822317253594081284811174​
50284102701938521105559644622948954930381964428810975665933446128475648233786783​
16527120190914564856692346034861045432664821339360726024914127372458700660631558​
81748815209209628292540917153643678925903600113305305488204665213841469519415116​
09433057270365759591953092186117381932611793105118548074462379962749567351885752​
72489122793818301194912983367336244065664308602139494639522473719070217986094370​
27705392171762931767523846748184676694051320005681271452635608277857713427577896​
09173637178721468440901224953430146549585371050792279689258923542019956112129021​
96086403441815981362977477130996051870721134999999837297804995105973173281609631​
85950244594553469083026425223082533446850352619311881710100031378387528865875332​
08381420617177669147303598253490428755468731159562863882353787593751957781857780​
53217122680661300192787661119590921642019893809525720106548586327886593615338182​
79682303019520353018529689957736225994138912497217752834791315155748572424541506​
95950829533116861727855889075098381754637464939319255060400927701671139009848824​
0128583616035637076601047101819429555961989467678374446

The correct value of Pi ends in 678374494 while our computed value ends in 678374446, so we've got 1250 correct decimals en just 10 iterations, which took 16.8 milliseconds .

2) Now let's compute your integer exponentiation (345^678) using a program which implements a loop similar to the one I used, which does 678 multiprecision integer multiplications:

      10 N=1:for I%=1 to 678:N*=345:next I%:print N


When run this produces the 1721-digit result I gave in my previous post and it takes just 0.941 milliseconds. However, as this result is 1721 digits long while the above computed value of Pi was 1252 digits, we'll time instead a power which results in 1252 digits as well, and that would be 345^493, which runs in 0.53 milliseconds.

Thus, the 1252-digit integer exponentiation is 16.8/0.53 = 32 times faster then the 1252-digit computed Pi, not the other way around.

If using the internal integer exponentiation routines instead of my one-line program, we find that computing the 1252 digits of 345^493 takes just 0.061 milliseconds, which is some 9 times faster than my 1-line program, and the 1721-digit 345^678 takes 0.091 milliseconds.

I hope this will answer your original post to your satisfaction.
Regards.

V.
.