Mostly off topic but maybe this post attracts people who know the answer to a question that I ran into when I implemented a big integer based rational number library some time ago.
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.
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.