<commit_before>#lang racket
(display "\nEXCERCISE 1.19\n")


; Let T be
;
;     a <- a + b
;     b <- a
;
; This will provide us with the fibonnaci sequence if applied repeatedly
;
; Now consider Tpq so that
;
;     a <- bq + aq + ap
;     b <- bp + aq
;
; Applying Tpq twice:
;
;     a1 <- bq + aq + ap
;     b1 <- bp + aq
;
;     a2 <- (bp + aq)q + (bq + aq + ap)q +(bq + aq + ap)p
;     b2 <- (bp + aq)p + (bq + aq + ap)q
;
;     a2 <- b(2qp + qq) + a(2qp + qq) + a(qq + pp)
;     b2 <- b(qq + pp) + a(2qp + qq)
;
; therefore, 
;
;     p' = qq + pp
;     q' = 2qp + qq
;
; Why do we care? 
;
; Because being able to square the fibonnaci transformation allows us to use 
; successive squaring to generate an iterative procedure for fibonnaci numbers 
; with logarithmic time complexity:


(define (half x) (/ x 2))

(define (fib n)
	(fibiter 1 0 0 1 n))

(define (p-prime q p)
	(+ (* q q) (* p p)))

(define (q-prime q p)
	(+ (* 2 q p) (* q q)))

(define (fibiter a b p q count)
	(display (format "~a ~a ~a ~a ~a\n" a b q p count))
	(cond 
		((= count 0)     b)
		((even? count)   (fibiter a b (p-prime q p) (q-prime q p)  (half count)))
		(else 			 (fibiter 
							(+ (* b q) (* a q) (* a p))
							(+ (* b p) (* a q))
							q
							p
							(- count 1)))))

(fib 3)
(fib 10)



<commit_msg>Fix typo causing issue with odd number on fib function<commit_after>#lang racket
(display "\nEXCERCISE 1.19\n")


; Let T be
;
;     a <- a + b
;     b <- a
;
; This will provide us with the fibonnaci sequence if applied repeatedly
;
; Now consider Tpq so that
;
;     a <- bq + aq + ap
;     b <- bp + aq
;
; Applying Tpq twice:
;
;     a1 <- bq + aq + ap
;     b1 <- bp + aq
;
;     a2 <- (bp + aq)q + (bq + aq + ap)q +(bq + aq + ap)p
;     b2 <- (bp + aq)p + (bq + aq + ap)q
;
;     a2 <- b(2qp + qq) + a(2qp + qq) + a(qq + pp)
;     b2 <- b(qq + pp) + a(2qp + qq)
;
; therefore, 
;
;     p' = qq + pp
;     q' = 2qp + qq
;
; Why do we care? 
;
; Because being able to square the fibonnaci transformation allows us to use 
; successive squaring to generate an iterative procedure for fibonnaci numbers 
; with logarithmic time complexity:


(define (dec x) (- x 1))

(define (naive-fib x)
	(cond 
		((= x 1) 1)
		((= x 2) 1)
		(else (+ (naive-fib (dec x)) (naive-fib (dec (dec x)))))))


(define (half x) (/ x 2))

(define (fib n)
	(fibiter 1 0 0 1 n))

(define (p-prime q p)
	(+ (* q q) (* p p)))

(define (q-prime q p)
	(+ (* 2 q p) (* q q)))

(define (fibiter a b p q count)
	;(display (format "~a ~a ~a ~a ~a\n" a b q p count))
	(cond 
		((= count 0)     b)
		((even? count)   (fibiter a b (p-prime q p) (q-prime q p)  (half count)))
		(else 			 (fibiter 
							(+ (* b q) (* a q) (* a p))
							(+ (* b p) (* a q))
							p
							q
							(- count 1)))))



(= (fib 7) (naive-fib 7))
(= (fib 10) (naive-fib 10))




{'fraction_non_alphanumeric': 0.18271954674220964, 'fraction_numerical': 0.019830028328611898, 'mean_word_length': 2.077342047930283, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '776059', 'n_tokens_mistral': 1403, 'n_tokens_neox': 1205, 'n_words': 430}