Re:LibBF – a small library to handle arbitrary precision flo...
by thaumasiotes on Wednesday March 07, 2018 @04:38AM
(#16535286)
> I implemented some cycle finding algorithm, a tortoise and hare variant maybe but I can not tell from the top of my head, on the reminder sequence giving up after a user-specified number of steps.
What's the cycle finding for? Isn't it enough to record the remainder sequence with indices? As soon as any remainder reoccurs, that's the cycle.
Re:LibBF – a small library to handle arbitrary precision flo...
by danbruc on Wednesday March 07, 2018 @12:52PM
(#16538232)
You could of course just maintain the set of remainders seen so far and then you would detect the cycle by reaching a remainder that is already in your set of remainders seen so far but that requires space proportional to the number of digits expanded and if you are expanding a lot of digits and have a large denominator, this will add substantially to the amount of memory consumed. The digits themselves require of course a linear amount of space, too, but only about one byte per digit compared to the potentially big remainder.
And unfortunately q is just way to loose as a bound if it even deserves the name bound in this case. I initially started looking into this because I wanted to print something like »0.577 215 664 <901,532 more digits>« but in that case q is essentially useless because you either have to really search the cycle which quickly becomes impractical once q reaches millions or billions or you have to live with »0.577 215 664 <up to 999,999,991 more digits but maybe also just one>«.