346 Long Decimal Fractions
Back to General discussions forum
I have a solution but my solution takes too long. My programming language is Julia. I use BigInt, divrem function, exponentiation and modulo to get the last digit. For the 18 items I need to solve I am in item 15 and it's taking forever. Can anyone recommend or provide a clue on what's a better way to solve this problem?
This problem was mistakenly marked with tag simple, but it is definitely from puzzles section, so I changed the tag.
It is valuable to give experience of assessing calculation complexity before trying to solve. To put it simple, author intentionally picked such limits that "straightforward" solution with long arithmetics is guaranteed to stuck in any language. As usual with puzzles, this task mainly makes sense if you find its cunning solution yourself. So perhaps it's better to think a bit more on it ourselves (I haven't solved it too yet) and skip for now if no enlightenment comes. Perhaps on the other attempt in a week or a month it may suddenly crack :)
It will be simple if the fractions are no larger than 10 digits.
True. But that would sort of defeat the point of the problem, which is to make the solver think.
at least it is easy to understand where to start thinking from - reading about decimal fractions, their periods,
conversion etc. The limit of 10^18 in the problem statement should instantly hint such long value won't fit any
computer memory, neither the program could do so many iterations in dozens years.