3 ms·
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 r
by danbruc 9y ago
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.