Leonardo Numbers

June 9, 2015

Our first implementation is the natural recursive definition, which has exponential time complexity:

(define (leo1 n) (if ( (time (leo1 30)) (time (leo1 30)) 2 collections 193 ms elapsed cpu time, including 1 ms collecting 193 ms elapsed real time, including 1 ms collecting 21541376 bytes allocated, including 16611696 bytes reclaimed 2692537

Our second implementation iterates through the sequence of Leonardo numbers, keeping track of the two prior numbers in the sequence, and operates in linear time:

(define (leo2 n) (if ( (time (leo2 30)) (time (leo2 30)) no collections 0 ms elapsed cpu time 0 ms elapsed real time 3376 bytes allocated 2692537 > (time (begin (leo2 250000) 'done)) (time (begin (leo2 250000) ...)) 612 collections 4475 ms elapsed cpu time, including 80 ms collecting 4492 ms elapsed real time, including 59 ms collecting 5459988896 bytes allocated, including 5457970720 bytes reclaimed done

Our third implementation uses matrix multiplication to compute the related Fibonacci number, as we did in a previous exercise; it operates in logarithmic time:

(define (fib n) (if (zero? n) 0 (matrix-ref (matrix-power #(#(1 1) #(1 0)) n) 1 0)))


(define (leo3 n) (- (* (fib (+ n 1)) 2) 1))

> (time (leo3 30)) (time (leo3 30)) no collections 0 ms elapsed cpu time 0 ms elapsed real time 34432 bytes allocated 2692537 > (time (begin (leo3 250000) 'done)) (time (begin (leo3 250000) ...)) 1 collection 340 ms elapsed cpu time, including 0 ms collecting 339 ms elapsed real time, including 0 ms collecting 2792832 bytes allocated, including 8361360 bytes reclaimed done > (time (begin (leo3 1000000) 'done)) (time (begin (leo3 1000000) ...)) 1 collection 5370 ms elapsed cpu time, including 1 ms collecting 5409 ms elapsed real time, including 0 ms collecting 10856992 bytes allocated, including 8591504 bytes reclaimed done

We don’t get the full logarithmic effect of the algorithm because the numbers involved are so big that the time to do arithmetic on them becomes significant; note that L_1000000 has 208988 digits. You can run the program at http://ideone.com/XQTUwK, where you will also see the matrix functions.

Posted by programmingpraxis

Filed in Exercises

6 Comments »

6 Responses to “Leonardo Numbers”

FA said
June 9, 2015 at 9:41 AM
In Scala as a stream:

def LeonardoNumbers(n1: Int = 1, n2: Int = 1): Stream[Int] = Stream.cons(n1, LeonardoNumbers(n2, n1+n2+1))
LeonardoNumbers() take 15 toList

//> res1: List[Int] = List(1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219)

Francesco said

June 9, 2015 at 11:15 AM

Haskell:

leo@(_:lt) = 1 : 1 : zipWith (\a b -> a + b + 1) lt leo

Graham said

June 9, 2015 at 4:09 PM

Python iterator in the usual fashion:

def leonardo_numbers():
    a, b = 1, 1
    while True:
        yield a
        a, b = b, a + b + 1

And in J, using this for matrix exponentiation:

lm=:1 1,:1 0			  NB. 2x2 matrix
mp=:+/ .*			  NB. matrix (inner) product
pow=: 4 : 'mp/ mp~^:(I.|.#:y) x'  NB. matrix exponentiation by repeated squaring
leonardo=:x:0{0{lm pow	      	  NB. 'leonardo 10' returns 89

haari said
June 10, 2015 at 7:58 AM
public class LeonardoNumbers {

public static void main(String[] args) throws NumberFormatException, IOException{

InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
System.out.println(“Enter the range to which leonard numbers should be printed”);
int n = Integer.parseInt(br.readLine());

LeonardoNumbers lnd = new LeonardoNumbers();
System.out.println(“Leonardo Series is as follows “);

int result = 0;
for(int i = 1;i<=n; i++){
result = lnd.leonardo(i);
System.out.print(" "+result);
}
}
private int leonardo(int n) {

if(n == 1)
return 1;
if(n == 2)
return 1;
else
return leonardo(n-1)+leonardo(n-2) + 1;

}
}

haari said

June 11, 2015 at 9:50 AM

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class LeonardoNumbers {

	
	public static void main(String[] args) throws NumberFormatException, IOException{
		
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		
		System.out.println("Enter the range to which leonard numbers should be printed");
		int n = Integer.parseInt(br.readLine());
		
		LeonardoNumbers lnd = new LeonardoNumbers();
		System.out.println("Leonardo Series is as follows ");
		int result = 0;
		for(int i = 1;i<=n; i++){
			result = lnd.leonardo(i);
			System.out.print(" "+result);
		}
	}

	private int leonardo(int n) {
			
		if(n == 1)
			return 1;
		if(n == 2)
			return 1;
		else
			return leonardo(n-1)+leonardo(n-2) + 1;
		
	}
}

Leonardo numbers | Wrong Side of Memphis said
June 13, 2015 at 12:24 AM
[…] saw this on Programming Praxis, and I like a lot the solution proposed by Graham on the comments, using an […]

Programming Praxis