{{ message }}

Instantly share code, notes, and snippets.

# jburse/fibluc.p

Last active Mar 29, 2016
 /** * Computing fibonacci and lucas numbers at the same time. * * Fn: n-th Fibonacci Number * Ln: n-th Lucas Number * * By this binary recursion step: * * F2n = Fn*Ln * L2n = (5*Fn^2+Ln^2)//2 * * And this linear recursion step: * * Fn+1 = (Fn+Ln)//2 * Ln+1 = (5*Fn+Ln)//2 * * Source: MATLAB Examples, Fibonacci Evolution, John D'Errico * https://www.mathworks.com/examples/matlab/community/11551-fibonaccievolution * * Copyright 2016, XLOG Technologies GmbH, Switzerland * Jekejeke Prolog 1.1.3 (a fast and small prolog interpreter) */ % fibluc(+Integer, -Integer, -Integer) fibluc(0, 0, 2). fibluc(1, 1, 1). fibluc(N, F, L) :- N > 1, N rem 2 =:= 1, M is N-1, fibluc(M, F1, L1), F is (F1+L1)//2, L is (5*F1+L1)//2. fibluc(N, F, L) :- N > 1, N rem 2 =:= 0, M is N//2, fibluc(M, F1, L1), F is F1*L1, L is (5*F1^2+L1^2)//2. % ?- fibluc(14, X, Y). % X = 377, % Y = 843
 /** * solution from lurker adapted to SICStus Prolog. * crashes with integer underflow for the 100 problem. */ :- use_module(library(clpfd)). fibluc(0, 0, 2). fibluc(1, 1, 1). fibluc(N, F, L) :- N in 2..1000, % Pick a reasonable value here for 1000 F #> 0, L #> 0, N rem 2 #= 1, M #= N-1, F #= (F1 + L1) // 2, L #= (5*F1 + L1) // 2, fibluc(M, F1, L1). fibluc(N, F, L) :- N in 2..1000, % Pick a reasonable value here for 1000 F #> 0, L #> 0, N rem 2 #= 0, M #= N // 2, F #= F1 * L1, L #= (5*F1*F1 + L1*L1) // 2, fibluc(M, F1, L1). % the 100 problem % ?- fibluc(100, X, Y), fibluc(N, X, Z).
 /** * solution from lurker for SWI-Prolog. * hangs on SWI 7.2.3 for the 100 problem. * supposedly good result for the 100 problem on SWI 7.1.33. * good result not yet verified on my side. */ :- use_module(library(clpfd)). fibluc(0, 0, 2). fibluc(1, 1, 1). fibluc(N, F, L) :- N in 2..1000, % Pick a reasonable value here for 1000 [F, L] ins 1..sup, N rem 2 #= 1, M #= N-1, F #= (F1 + L1) // 2, L #= (5*F1 + L1) // 2, fibluc(M, F1, L1). fibluc(N, F, L) :- N in 2..1000, % Pick a reasonable value here for 1000 [F, L] ins 1..sup, N rem 2 #= 0, M #= N // 2, F #= F1 * L1, L #= (5*F1*F1 + L1*L1) // 2, fibluc(M, F1, L1). % the 100 problem % ?- fibluc(100, X, Y), fibluc(N, X, Z).
 /** * second solution from lurker for SWI-Prolog. * supposedly good result for the 100 problem on SWI 7.2.3. * good result not yet verified on my side. */ :- use_module(library(clpfd)). fibluc(0, 0, 2). fibluc(1, 1, 1). fibluc(N, F, L) :- N in 2..1000, % Pick a reasonable value here for 1000 [F, L] ins 1..sup, N rem 2 #= 1, M #= N-1, fibluc(M, F1, L1), F #= (F1 + L1) // 2, L #= (5*F1 + L1) // 2. fibluc(N, F, L) :- N in 2..1000, % Pick a reasonable value here for 1000 [F, L] ins 1..sup, N rem 2 #= 0, M #= N // 2, fibluc(M, F1, L1), F #= F1 * L1, L #= (5*F1*F1 + L1*L1) // 2. % the 100 problem % ?- fibluc(100, X, Y), fibluc(N, X, Z).

### jburse commented Mar 28, 2016

 Can this be turned into a CLP(FD) program preserving the fast recursion and at the same time making it bidirectionally, for example figuring out the index n for Fn=377? If yes how? If not why? http://stackoverflow.com/questions/36264421/clpfd-ying-simultaneous-recursion-for-fibonacci-lukas-numbers-possible

### triska commented Mar 28, 2016

 Very nice question! Only one comment: Even if it is not currently bidirectional, is there any reason you are still using `(is)/2` although you know that all quantities are integers? In my experience, a good first step to help beginners with the introduction or transition to purer methods is to start using `(#=)/2` right away when dealing with integers. In fact, I highly recommend to make CLP(FD) constraints available right from the start in Prolog systems, like in GNU Prolog! You can only win this way, and then let us tackle the omnidirectionality aspect on top of that, starting from a more declarative basis. At least that's how I see it. Is there any chance that you go in this direction with Jekejeke Prolog? I think this would be a great innovation, and put Jekejeke ahead of several other systems at least in that important respect. In fact, systems that do not make this step are in my view only delaying the inevitable.

### jburse commented Mar 28, 2016

 Jekejeke Minlog which contains CLP(FD) is still beta, there is no distribution license, only an evaluation license, its not yet supposed to be bundled by any means.