LibBF – a small library to handle arbitrary precision floating point numbers
bellard.org
bellard.org
Does anyone know how LibBF stacks up against GMP? [5]
[3] https://bellard.org/jslinux/
[5] https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithme...
I like the stuff he did for software radio decoding too.
GET OUT OF TOWN.
The decimal representation of a rational number p / q has the general form ±<integer part>.<non-repeating fractional part>(<repeating fractional part>), for example 41,111,111 / 333,000 equals 123.456(789). Is there an efficient algorithm to determine the lengths of the fractional parts or one that does at least provides reasonably tight bounds on them?
I did quite a bit of research at the time but only with limited success. I am reasonably sure that finding the exact lengths is comparable in hardness to factoring p and q in some cases and possibly harder in the general case. But I did not come across much with regard to bounds on the lengths.
Maybe there was somewhere an implicit answer to my question which I did not recognize or fully appreciate due to my limited knowledge of number theory but I never came across an explicit statement that said that printing the decimal representation of a rational number or estimating its length is a hard or unsolved problem.
I ended up just performing the expansion digit by digit until I detected a cycle or reached a specified maximum length, but it would by nice to know in advance how long it will be or at least to learn that this is actually an hard or unsolved problem.
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>«.
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.
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 that Euler's totient function is "always 'nearly n'" in magnitude (Hardy and Littlewood), so that representation will be very expensive for most fractions of large denominator.
[0]: https://en.wikipedia.org/wiki/Repeating_decimal [1]: https://en.wikipedia.org/wiki/Euler%27s_totient_function
I still remember that quite well because that was probably the first and only time that I was unable to find someone stating that we do not know any better, and not only the Wikipedia article but everywhere I looked there was no such statement to be found. I eventually gave up after a couple of evenings but it obviously kept stuck somewhere in my mind and that is why I wrote the initial comment.
Finding the order of an element in a group is a hard problem on par with factoring http://mathworld.wolfram.com/GroupOrder.html
I'm not sure about cases where the state space doesn't form a multiplicative group, but I doubt that it gets much easier.
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 that it is not harder than division?
Edit: from the wikipedia section you link:
> If k = 2^a·5^b·n where n > 1 and n is not divisible by 2 or 5, then the length of the transient of 1/k is max(a,b) and the period [of the repetend, presumably] is r, where r is the smallest integer such that 10^r ≡ 1 (mod n)
All integers (except those whose only prime factors are 2 and 5) satisfy this condition, so this would appear to be exactly the method desired? Repeatedly dividing by 5 is much, much easier than factoring is. Taking the discrete log of 1... could be equivalent to factoring.
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).
Look at the Wikipedia page on repeated decimals and you can see many of the repeated sequences have length (q-1) ((q-1) is phi(q) when q is prime) [2].
There's a SO answer that talks about this [3]. I think I can derive it here, though take it with a grain of salt as I might have screwed something up.
Say you have a rational number p / q, and w.l.o.g., p < q. Consider an integer, R, that corresponds to the repeated portion of the rational number (in base 10), with length s (in decimal). This implies:
p/q = R sum_{k=1}^{\infty} 10^{-s k} = R / ( 10^s - 1 )
p (10^s - 1) - q R = 0
So to make the above equation true, let's be coarse and choose s = phi(q) in the below:
.. p (10^{ phi(q) } - 1 ) - q R = 0
-> p ( C q ) - q R = 0
-> q ( p C - R ) = 0
There's also the case of when 10 and q aren't relatively prime that needs to be worked out.
You can also see how this argument could be modified to work with other bases.
[1] https://softwareengineering.stackexchange.com/a/192077
[2] https://en.wikipedia.org/wiki/Repeating_decimal#Decimal_expa...
[1] https://math.stackexchange.com/questions/837489/algorithms-f...
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, disclaimers, or compromise, C is still king.
Could this have practically been written in rust? haskell? ...and still have the same degree of embeddability and reach?
Rust's runtime is comparable to C's. It is less portable because it uses LLVM as a backend, not because of the runtime.
> Then again, debugging segfaults isn't for everyone, so most are fine giving up C.
Depending on the application, having vulnerabilities due to undefined behavior is a much bigger problem than having to debug segfaults.
I wouldn't say LLVM is such a great restriction, except when talking about embedded (too few architectures supported here). The major desktop and server architectures are supported (AFAIK), even WASM.
GHC Haskell Runtime:
1. Comment out the malloc.h include in tinypi.c.
2. Add -Wno-unused-function to CFLAGS.
3. Use shasum, rather than sha1sum, in the test target.
I thought the best known multiplication algorithms (the ones based on Fourier transforms) for large numbers are a little slower than O(N log(N)). Has something better been found?
Looking forward to benchmarking this in a wasm context.
we're already deep down the EMSCRIPTEN_BINDINGS() rabbit-hole :)
originally, the fixed size heap (/w optimisations) meant unbound use from a JS lib was too hard to reason about; hence avoided entirely in favour of a emscripten blackbox.
Who will do the autotooling and repo hosting? I've added some sugar in my fork on github https://github.com/rurban/libbf/tree/my but I'm not sure yet if I will use it.
But the low constant overhead for small numbers, the small size, no assembler tricks and the MIT license makes it very attractive.
(JSON also does not permit infinities or NaN, which JavaScript does permit.)