Closed murilocamargos closed 6 years ago
Good one, @fredericojordan, I totally forgot about that 😅
@murilocamargos You can use the Ruby script add_new_problem
to automagically create directories and problem description readme files.
@FrankKair and @fredericojordan, thanks! I did forget that...
@caian-gums you gave a nice ideia about not computing pow
every time but I couldn't do it with bit masks. Instead I created a list to store powers of 10 from 0 to 9. This increased a lot the performance. The new version's stats:
Real time: 0.183 s
User time: 0.150 s
Sys. time: 0.022 s
CPU share: 94.42 %
Exit code: 0
Nice! I wrote, posted and thought that you cannot do that with bitmasks. That's why I deleted the comment 😅.
But it's nice to see that you think of another solution that increased the processing time!
How the solution works
The main advantage of this solution is that we only keep track of the first 9 and last 9 digits of the Fibonacci number (the important ones). The last 9 is easy, we only need to mod with 1e9, the first 9 is trickier. In order to do that, a math manipulation was needed.
Considering a Fibonacci number can be given by
round(phi^n/sqrt(5))
, we can uselog10
to storelog10(Fn)
as double and transform it again tolong
taking advantage of the size limits of this C type. Another optimization was checking if a number is 1-9 pandigital using bitwise operations instead of transforming the number into a string.Performance
C