[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/RomAjszt    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on May 31:
; square roots

(define (bisect n)
  (let loop ((lo (if (< 1 n) 1. n)) (hi (if (< 1 n) n 1.)))
    (display lo) (display " ") (display hi) (newline)
    (let ((mid (/ (+ lo hi) 2)))
      (cond ((< (abs (- (/ (* mid mid) n) 1)) 1e-14) mid)
            ((< (* mid mid) n) (loop mid hi))
            (else (loop lo mid))))))

(define (heron n) ; x' = (x + (n/x)) / 2
  (let loop ((x 1.))
    (display x) (newline)
    (let ((x-prime (/ (+ x (/ n x)) 2)))
      (if (< (abs (- (/ (* x x-prime) n) 1)) 1e-14)
          (/ (+ x x-prime) 2)
          (loop x-prime)))))

(define (newton n) ; x' = x - (x^2 - n) / 2x
  (let loop ((x 1.))
    (display x) (newline)
    (let ((x-prime (- x (/ (- (* x x) n) (+ x x)))))
      (if (< (abs (- (/ (* x x-prime) n) 1)) 1e-14)
          (/ (+ x x-prime) 2)
          (loop x-prime)))))

(define (optimize n) ; using heron's method
  (if (< n 1) (* 1/2 (optimize (* n 4)))
    (if (<= 4 n) (* 2 (optimize (/ n 4)))
      (let ((x (/ (+ 1. n) 2)))
        (let ((x (/ (+ x (/ n x)) 2)))
          (let ((x (/ (+ x (/ n x)) 2)))
            (let ((x (/ (+ x (/ n x)) 2)))
              (let ((x (/ (+ x (/ n x)) 2)))
                (let ((x (/ (+ x (/ n x)) 2)))
                  x)))))))))

(display (bisect 125348)) (newline) (newline)
(display (bisect 0.8)) (newline) (newline)

(display (heron 125348)) (newline) (newline)
(display (heron 0.8)) (newline) (newline)

(display (newton 125348)) (newline) (newline)
(display (newton 0.8)) (newline) (newline)

(display (optimize 125348)) (newline) (newline)
(display (optimize 0.8)) (newline) (newline)


Output:
1.0 125348
1.0 62674.5
1.0 31337.75
1.0 15669.375
1.0 7835.1875
1.0 3918.09375
1.0 1959.546875
1.0 980.2734375
1.0 490.63671875
245.818359375 490.63671875
245.818359375 368.2275390625
307.02294921875 368.2275390625
337.625244140625 368.2275390625
352.9263916015625 368.2275390625
352.9263916015625 360.57696533203125
352.9263916015625 356.7516784667969
352.9263916015625 354.8390350341797
353.8827133178711 354.8390350341797
353.8827133178711 354.3608741760254
353.8827133178711 354.12179374694824
354.00225353240967 354.12179374694824
354.00225353240967 354.06202363967896
354.0321385860443 354.06202363967896
354.0321385860443 354.04708111286163
354.039609849453 354.04708111286163
354.0433454811573 354.04708111286163
354.0433454811573 354.04521329700947
354.0442793890834 354.04521329700947
354.0447463430464 354.04521329700947
354.04497982002795 354.04521329700947
354.0450965585187 354.04521329700947
354.0451549277641 354.04521329700947
354.0451841123868 354.04521329700947
354.0451841123868 354.0451987046981
354.04519140854245 354.0451987046981
354.04519140854245 354.0451950566203
354.04519323258137 354.0451950566203
354.0451941446008 354.0451950566203
354.04519460061056 354.0451950566203
354.0451948286154 354.0451950566203
354.0451948286154 354.04519494261785
354.0451948286154 354.04519488561664
354.0451948286154 354.04519485711603
354.0451948428657 354.04519485711603
354.0451948499909 354.04519485711603
354.0451948535534 354.04519485711603
354.0451948535534 354.0451948553347
354.04519485444405 354.0451948553347
354.04519485488936 354.0451948553347
354.0451948551121 354.0451948553347
354.0451948551121 354.0451948552234
354.0451948551121 354.0451948551677
354.0451948551121 354.0451948551399
354.0451948551121 354.045194855126
354.045194855119

0.8 1.0
0.8 0.9
0.8500000000000001 0.9
0.875 0.9
0.8875 0.9
0.89375 0.9
0.89375 0.8968750000000001
0.89375 0.8953125000000001
0.89375 0.89453125
0.894140625 0.89453125
0.8943359375 0.89453125
0.8943359375 0.89443359375
0.8943847656249999 0.89443359375
0.8944091796875 0.89443359375
0.89442138671875 0.89443359375
0.89442138671875 0.894427490234375
0.8944244384765625 0.894427490234375
0.8944259643554687 0.894427490234375
0.8944267272949218 0.894427490234375
0.8944271087646484 0.894427490234375
0.8944271087646484 0.8944272994995117
0.8944271087646484 0.89442720413208
0.8944271564483641 0.89442720413208
0.8944271802902221 0.89442720413208
0.8944271802902221 0.8944271922111511
0.8944271862506865 0.8944271922111511
0.8944271892309188 0.8944271922111511
0.8944271907210349 0.8944271922111511
0.8944271907210349 0.8944271914660931
0.8944271907210349 0.894427191093564
0.8944271909072994 0.894427191093564
0.8944271909072994 0.8944271910004317
0.8944271909538655 0.8944271910004317
0.8944271909771486 0.8944271910004317
0.8944271909887902 0.8944271910004317
0.8944271909946109 0.8944271910004317
0.8944271909975212 0.8944271910004317
0.8944271909989765 0.8944271910004317
0.8944271909997041 0.8944271910004317
0.8944271909997041 0.8944271910000678
0.894427190999886 0.8944271910000678
0.894427190999886 0.8944271909999769
0.894427190999886 0.8944271909999315
0.8944271909999087 0.8944271909999315
0.8944271909999202

1.0
62674.5
31338.249992022273
15671.12491623693
7839.561788117747
3927.7754735639414
1979.844351517673
1021.5781996033152
572.1392735077299
395.612894666841
356.2289882689982
354.0518885182295
354.04519491839494
354.04519485512014
354.04519485512014

1.0
0.9
0.8944444444444445
0.8944271911663216
0.894427190999916
0.894427190999916

1.0
62674.5
31338.249992022273
15671.124916236928
7839.561788117746
3927.775473563941
1979.8443515176727
1021.578199603315
572.1392735077299
395.612894666841
356.22898826899814
354.0518885182295
354.04519491839494
354.04519485512014
354.04519485512014

1.0
0.9
0.8944444444444445
0.8944271911663216
0.8944271909999159
0.894427190999916

354.04519485512014

0.894427190999916



Create a new paste based on this one


Comments: