Re:LibBF – a small library to handle arbitrary precision flo...
by danbruc on Wednesday March 07, 2018 @01:02PM
(#16538335)
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).
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.