Decimal digits vs integer digits

[pier4r]

Reading from time to this posts like this:
http://www.hpmuseum.org/forum/thread-10108.html

let me reflects that for some numbers people have developed quite efficient way to get a lot of decimal digits. Instead the task to get integer digits of a large number, starting from relatively simple approaches (+1) or others (powers, factorial, logs, whathever), is quite hard.

For the little that I know, while we may extract hundreds/thousands of decimal digits for a square root with our calculators, getting the same for an integer number is not always that easy.

Dunno compute 345^678 , this may be a number that would require quite a lot of work for a lot of calculators (maybe not the prime/50g).

My guess is: decimal digits somehow can be extracted with a relatively simple approach (think about the algorithm for the square root) that keeps track of a little leftover to work on after every iteration.

The integer digits, instead, have to use on the entire work done until that point, so the complexity of every iteration just increases.

[Dieter]

(02-21-2018 11:22 AM)pier4r Wrote:  For the little that I know, while we may extract hundreds/thousands of decimal digits for a square root with our calculators, getting the same for an integer number is not always that easy.

I don't know why you distinguish between the digits left and right of the decimal point. Let's say you want to calculate

11^32 = 2111377674535255285545615254209921

This is an integer. But is this really more complicated than

1,1^32 = 21,11377674535255285545615254209921

If it is, simply calculate the latter and shift the decimal point. ;-)

(02-21-2018 11:22 AM)pier4r Wrote:  Dunno compute 345^678 , this may be a number that would require quite a lot of work for a lot of calculators (maybe not the prime/50g).

345^678 = 10^(678 * lg 345). The term in brackets is 678*2,5378... = 1720,6413..., so if calculating with many decimal digits is easy, this is easy as well. Take the fractional part of the result, i.e. 0,6413... (look, only decimal digits, that must be easy ;-)) and determine the antilog 4,3787... – and you already got the result 4,3787...E+1720. You just need the mantissa (4,3787...) with 1720 decimal digits. Which, you say, is not too difficult.

OK, OK – I think you got the idea. ;-)
No, I do not think that integers are easier or harder than decimals.

Dieter

[pier4r]

(02-21-2018 07:46 PM)Dieter Wrote:  No, I do not think that integers are easier or harder than decimals.

Dieter

Aside from the "semantic flaws" of my post, you got the idea of what I mean.

In other words, how come that for some numbers we can compute a lot of seemingly random digits (example: pi), but for numbers that grow we have difficulties.
There should be an underlying property that makes the latter harder.

I mean computing the digits of 10^1000 is not difficult, as other particular numbers, but those 1720 digits of 345^678 are pretty intensive to compute and I do not know any number that has seemingly random digits (and it is not derived from a power of two, like the Marsenne primes or possible primes) that was computed to many digits like pi.

[Valentin Albillo]

pier4r Wrote:In other words, how come that for some numbers we can compute a lot of seemingly random digits (example: pi), but for numbers that grow we have difficulties.
There should be an underlying property that makes the latter harder.

I mean computing the digits of 10^1000 is not difficult, as other particular numbers, but those 1720 digits of 345^678 are pretty intensive to compute and I do not know any number that has seemingly random digits (and it is not derived from a power of two, like the Marsenne primes or possible primes) that was computed to many digits like pi.

Nope. Have a look at this thread of mine, look at the very end where I give my solution to Take 5:

Short & Sweet Math Challenge 15.

You will find a short, 9-line program which I wrote to quickly and effortlessly compute the 19729-digit integer answer.

V.
.

[pier4r]

Thanks for the link!

Anyway I wrote "and it is not derived from a power of two, like the Marsenne primes", exactly because many large numbers, that have a large integer part, that I saw are power of two with some (relatively small) additions or subtractions.

Take 5 result to compute:
\[ 2^{65536} - 3 \]

PS: Valentin, how is going with the place for publishing your contributions? Was the wiki not enough?

[Valentin Albillo]

.
Hi again,

(02-21-2018 10:02 PM)pier4r Wrote:  Anyway I wrote "and it is not derived from a power of two, like the Marsenne primes", exactly because many large numbers, that have a large integer part, that I saw are power of two with some (relatively small) additions or subtractions.
Take 5 result to compute: 2^{65536} - 3

This is irrelevant, the 9-line routine in the link I posted is a general integer x^y procedure, which in the link was merely particularized to the case 2^65536-3 in order to run as fast as possible, which was necessary considering the 19729-digit result.

Just changing a few constants here and there and removing an unnecessary MOD and the final "-3" will particularize it for your 345^678 case, namely:

HP-71B BASIC 276 bytes

1 DESTROY ALL @ OPTION BASE 0 @ N=678 @ M=9 @ DIM A(1) @ K=10^M
2 A(0)=1 @ P=0 @ R=345 @ FOR J=0 TO N-1 @ MAT A=(R)*A @ GOSUB 7
3 IF NOT MOD(J,3) THEN DIM A(UBND(A,1)+1)
4 NEXT J @ J=0 @ DISP @ DISP STR$(A(P));
5 FOR I=P-1 TO 0 STEP -1 @ J=J+1 @ IF J=8 THEN DISP @ J=0
6 A$=STR$(A(I)) @ DISP RPT$("0",M-LEN(A$));A$; @ NEXT I @ DISP @ END
7 FOR I=0 TO P @ A(I+1)=A(I+1)+A(I) DIV K @ A(I)=MOD(A(I),K) @ NEXT I
8 P=P+SGN(A(P+1)) @ RETURN


>RUN

       43787127894257936017120551659989811782288595515354488987325413900
802341364764426050357758027764875852954092964869040837522986085325699173
440208660552897860597656352894886234825033019524427828510385113091870587
005237979574624235528306024867516223687363549218278200731353323503043912
120989668489236868998861750420042665298754353038576710971046242429801586
669131859077306402007714558887393358830404516840817948233451328963360193
114563267109108960521839713831465439944710989493035683991255640279032860
581765608574303767665601432793221493427233670620749461059260365310968431
585830459166695451811726296981933487119148771459810108174762065159568198
407266299590937256706240056624384072905607134849197301523581457759856051
111607090600538618993962407324224698618801995078569897879194293395864756
550058758882360360608188838042731105482307344218732065369684380408154422
235201486556127538160893294416739548640206983367006318379868072916894831
076832048085751609655811267096468212505533782955677349524900995963177834
200313830363586547412870379485068164058291348085768726434048158469207076
703493830888308971397858159094316029849039124281681570344592276962513399
638111721953436191496696440051270541907304501831480363885440523615788049
760816385876587151965017830052548542015425762584641347565586651012967162
073436892709365750805457343388826858826999648631383565305483943145460008
131395931429816939097414831715038496546088196375343408059976593548460657
131204675259681017973097295388536257824843287263600409978735955744310463
706641029042353833038949463564702481944217729382576380928106704511758276
752884386737114453127433596534637098769025716578727297063727391809360711
921656764151908265461416144338248346290498602684237994253635406494140625

This takes just 19 seconds in Emu71 on a very old pc to get the 1721-digit result you saw above.

Quote:PS: Valentin, how is going with the place for publishing your contributions? Was the wiki not enough?

I'm still not satisfied with the options I've been looking, my ideal continues to be some HP-fan who would kindly host my files but meanwhile I'm still looking and the materials continue to accumulate, which is bad if I can't get them available somewhere. I think I've got enough for a dozen articles and scores of challenges and short columns.

Thanks for your interest and best regards.
V.
.

[pier4r]

(02-22-2018 12:14 AM)Valentin Albillo Wrote:  This takes just 19 seconds in Emu71 on a very old pc to get the 1721-digit result you saw above.

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?

[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.
.

[pier4r]

(02-23-2018 02:52 AM)Valentin Albillo Wrote:  I hope this will answer your original post to your satisfaction.
Regards.

V.
.

It is surely interesting content but I would have expected also a comparison with growing digits, to see the trend.

What I mean is the following. You showed that using the multiprecision arithmetic built in the basic interpreter of the hp 71 ROM (nice, by the way), you can compute my example faster than an equivalent number of digits of Pi.

That's ok, it is a fact. But it is an answer like "look, we have g(x) and f(x). When x is 1250, f(x) is smaller than g(x)". Nice, but can I use it to say "and surely, since x=1250 is pretty large, we can conclude that f(x) will be always smaller than g(x) for any x larger than 1250" ? As far as I know, no.

In other words, what is the upper bound (in terms of time and/or memory) of functions used to compute the digits of pi (or square roots) compared to functions used to compute large numbers?

This considering the limitation of the computing hardware. If we would have hardware capable of infinite precision operations (so not 16, 32, 64 or whatever bits) then my question may be not that interesting.

Instead considering the limit of the operations, so say with 16 bit registers at most, I have the feeling (since I did not dig in the formulas yet) that computing square roots or digits of pi requires more or less constant time for the same number of digits extracted. This using optimized algorithms.

Instead for large numbers the work (I think) grows and grows , as one need to consider the previous results to compute the new one, and the previous result is getting larger.

[speta]

May i know whether the functionality and the usage is same when compared other brand calculators and also i want to know how its different from regulars one.