We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I passed all tests by using the Karatsuba multiplication algorithm with my own Big Integer implementation. Very dumb by the way, but fast enough to find the 24 modified Fibonacci number in a half of second (0 1 24).
Nothing special work was done about working with number representation – store it as is in a base 10 in a vector. If it is still relevant for you, email me (taenaru@gmail.com) and I'll gladly explain you how it might work.
It's a waste of dev time, imho. Karatsuba algo replaces 2mul+1add with 1mul+4add. They say mul takes 3-4 times cycles of add these days, so you gonna get max 12.5% speed up (or zero, if it's actually 3 times) for the code which probably takes less than 20% of execution time (memory access will be the bottleneck, not number crunching)
Fibonacci Modified
You are viewing a single comment's thread. Return to all comments →
I passed all tests by using the Karatsuba multiplication algorithm with my own Big Integer implementation. Very dumb by the way, but fast enough to find the 24 modified Fibonacci number in a half of second (0 1 24). Nothing special work was done about working with number representation – store it as is in a base 10 in a vector. If it is still relevant for you, email me (taenaru@gmail.com) and I'll gladly explain you how it might work.
can you send me explaination
nickholden786@gmail.com
It's a waste of dev time, imho. Karatsuba algo replaces 2mul+1add with 1mul+4add. They say mul takes 3-4 times cycles of add these days, so you gonna get max 12.5% speed up (or zero, if it's actually 3 times) for the code which probably takes less than 20% of execution time (memory access will be the bottleneck, not number crunching)
No need for that young fella 🧐
JAVA SOLUTION
100% TEST CASES ✅
COMPLEXITY IN 0(N) TIME
but we have to return int value not string, so how we can do that
''' static BigInteger fibonacciModified(int t1, int t2, int n) { BigInteger[] arr = new BigInteger[n]; BigInteger tOne = new BigInteger(Integer.toString(t1)); BigInteger tTwo = new BigInteger(Integer.toString(t2)); arr[0] = tOne; arr[1] = tTwo; for(int i = 2; i < n; i++){ BigInteger iMinus1BigInteger = arr[i - 1]; BigInteger iMinus2BigInteger = arr[i - 2]; BigInteger powered = iMinus1BigInteger.pow(2); BigInteger poweredAndSum = powered.add(iMinus2BigInteger); arr[i] = poweredAndSum; }''' BigInteger result = arr[n-1];