Skip to content

Instantly share code, notes, and snippets.

@jburse

jburse/fibluc.p

Last active Mar 29, 2016
Embed
What would you like to do?
/**
* 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

This comment has been minimized.

Copy link
Owner Author

@jburse 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

This comment has been minimized.

Copy link

@triska 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

This comment has been minimized.

Copy link
Owner Author

@jburse 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.

Minlog Logo
https://play.google.com/store/apps/details?id=jekmin.platform.headless

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.