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.

Advertisements

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

    Haskell:

    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{

    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;

    }
    }

  5. haari said
    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;
    		
    	}
    }
    
  6. […] saw this on Programming Praxis, and I like a lot the solution proposed by Graham on the comments, using an […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: