Created
May 4, 2022 19:45
-
-
Save DedSec256/38c128db75ccc4525a4064db58dd6a63 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (* | |
| * --------------------------------------------- | |
| * Introduction: | |
| * --------------------------------------------- | |
| * We know that (F0 F1) * P^n = (Fn Fn+1), | |
| * where P = (0 1) and F0 = 0, F1 = 1 | |
| * (1 1) | |
| * | |
| * => P^n = (a b) => (F0 F1) * (a b) = (Fn Fn+1) | |
| * (c d) (c d) | |
| * => Fn = F0 * a + F1 * c = c | |
| * | |
| * --------------------------------------------- | |
| * Action plan: | |
| * --------------------------------------------- | |
| * Find P^n => get c => find Fn 😏 | |
| *) | |
| let fibonacci n = | |
| (* Standart square matrix multiply *) | |
| let matrixMuliply (A00, A01, A10, A11) (B00, B01, B10, B11) = | |
| (* A = (A00 A01), B = (B00 B01) *) | |
| (* (A10 A11) (B10 B11) *) | |
| ( (A00 * B00) + (A01 * B10), (A00 * B01) + (A01 * A11), | |
| (A10 * B00) + (A11 * B10), (A10 * B01) + (A11 * B11) ) | |
| (* Binary pow *) | |
| let rec fastMatrixPow A n = | |
| if n = 1 then A | |
| elif n % 2 = 0 then | |
| let B = fastMatrixPow A (n / 2) | |
| matrixMuliply B B | |
| else matrixMuliply (fastMatrixPow A (n - 1)) A | |
| let (_, _, c, _) = fastMatrixPow (0, 1, 1, 1) n | |
| c |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment