LibBF – a small library to handle arbitrary precision floating point numbers • Hacker News Board

Re: LibBF – a small library to handle arbitrary precision floating point numbers

#61

Post by danbruc » Wed, Mar 07, 2018, 5:52 PM UTC

thaumasiotes wrote: post #44

danbruc wrote: post #17

Earlier quoted context omitted.

That is exactly what I did, 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. But it irks me that this may abort just a hand full of steps before finally finding the cycle. And unfortunately q is just way to loose as a bound if it even deserves the name bound in this case.…

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

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.

Re: LibBF – a small library to handle arbitrary precision floating point numbers

#62

Post by danbruc » Wed, Mar 07, 2018, 6:02 PM UTC

thaumasiotes wrote: post #41

mrmr1993 wrote: post #13

Earlier quoted context omitted.

As you said, this is equivalent to factorisation in terms of complexity. The Wikipedia article[0] on the subject does a good job of summarising the details of this in the section "Other properties of repeatend lengths". For a simple answer, the lengths are bounded above by Euler's totient function [1] (the sum of factors) of the denominator. Any tighter bounds depend on the specific primes in the factorisation. Note…

> As you said, this is equivalent to factorisation in terms of complexity. This can't be right. Factorisation is, legendarily, a hard problem, unsolved (in realistic time frames) for large input. But more than that, it's harder than division is. Finding the length of the nonrepeating and repeating parts of a rational number's decimal expansion can be done just by doing the division. That would appear to be evidence t…

That would appear to be evidence that it is not harder than division?

From your edit I guess that you already realized this, but the hard part here is that for 1 / q you would have to perform up to q divisions of integers of size n = log₂(q) which of course takes time O(2ⁿ) even assuming the divisions are O(1).

Re: LibBF – a small library to handle arbitrary precision floating point numbers

#63

Post by blt » Thu, Mar 08, 2018, 9:36 AM UTC

peatmoss wrote: post #49

Perhaps a side digression to this conversation, but... in spite of all the cool languages we talk about that have many on-paper advantages of either safety, convenience, or support of paradigms, is there really any option besides C for this kind of thing? It still seems that, if you want to write Core Infrastructual Code that can be run anywhere, on anything, that links with any other software without any caveats, di…

Fortran, assembler