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 L1000000 has 208988 digits. You can run the program at http://ideone.com/XQTUwK, where you will also see the matrix functions.

Pages: 1 2

6 Responses to “Leonardo Numbers”

1. FA said

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)

2. Francesco said

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

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

4. haari said

public class LeonardoNumbers {

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

System.out.println(“Enter the range to which leonard numbers should be printed”);

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;

}
}

5. haari said
import java.io.IOException;

public class LeonardoNumbers {

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

System.out.println("Enter the range to which leonard numbers should be printed");

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;

}
}

6. […] saw this on Programming Praxis, and I like a lot the solution proposed by Graham on the comments, using an […]