Counting repeated additions to estimate an integer quotient is silly. Knuth Vol 2 has bignum algorithms for both Euclidean and binary GCD. In both cases, you run a toy algorithm using just a few bytes of the operands. This will behave initially like the full precision process. Record the steps in a matrix of smallnums. About when the toy process runs out of significance, or when the smallnums threaten largeness, discard its state and apply the matrix to the two bignums. This will make them smaller, and in the binary case, much "evener". It doesn't matter if the last few terms or bits were wrong--the process is self-correcting. It will simply cough up a few nonpositive terms which can be smoothed out in (sub?)linear time. --rwg Date: 2016-12-11 10:53 From: Simon Plouffe <simon.plouffe@gmail.com> Hello, yes, speaking of wich, To go from a decimal number to continued fraction there is one simple algorithm that uses only additions. You just need a for-next loop, you start with x0 (supposedly fractional) Start with S0= 0. do Sn+1 = Sn+Xn, until Xn+1 is greater than 1. Output the index n (the partial quotient). X0 = Xn+1 od: In principle this is clean, no inverse to compute. The only drawback of this method is that when the partial quotient is really big then the procedures hangs. But if the number is believed to be non-exotic, well, that's a living. The big advantage is that the computation can be carried out to billions of digits wide with not much overhead, it is a bit slow perhaps but very economical in memory. Does this have ever been attempted on a big number like Pi ?? Question : what is the cost of operations to inverse a number of let's say 22459 billion digits ?? a lot ? it could be improved with this trick. When you have a certain X0 in the process - Evaluate roughly the ratio of 1/X0 = ratio , (let's say to 50 digits) then multiply the big number by that [ ratio ] + 1 , [ ] being the integer part. For all practical purpose the ratio won't be bigger than 20-30 digits. so this is simple in fact, only 1 multiplication by 1 number of limited size. Too simple ? Best regards, Simon Plouffe Le 2016-12-11 à 18:04, Bill Gosper a écrit :
Digits. Feh. What a waste of chips and neurons. The only excuse: Now that they've done it, converting to the continued fraction might be slightly easier than extracting the cf directly. But if you want both, it might be easier to extract the decimal from the cf. Or maybe not, since they probably wrote their own multiprecision routines to use base 10^19 vs 2^64 to dodge the big radix conversion cost. Or is floating point still so much faster than fixed that they sacrificed several digits per "word" to redundant exponents, like the old Mersenne finders? --rwg
Date: 2016-12-10 17:53 From: Simon Plouffe <simon.plouffe@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Reply-To: math-fun <math-fun@mailman.xmission.com>
They made a new computation record of Pi,
http://www.numberworld.org/y-cruncher/records.html
22 459 157 718 361 digits.
This is big.
the digits seems to be rather normal in base 10 and 16.
https://arxiv.org/ftp/arxiv/papers/1612/1612.00489.pdf
also : 22.459157718361 is Pi^E.
Some explanations here : http://pi2e.ch/
best regards, Simon Plouffe