lambdaway
::
reduce
1
|
list
|
login
|
load
|
|
;; _img data/amelie_poulain.jpg ;; {center I love reducing the lambada!} _img data/FB_IMG_16167536219181.jpg _h1 [[iter]] | reduce | [[sylvester]] | [[iterations|?view=reduce2]] {center see also [[reduce3]]} _p Replacing tail-recursion by iteration built on {b reduce} and a {b {u small} local array}. _p First of all: {prewrap '{S.reduce long_mult {S.serie 1 100}} -> {S.reduce long_mult {S.serie 1 100}} } _h2 1) fac {prewrap 1) tail-recursive version '{def tfac {lambda {:a :n} {if {> :n 0} then {tfac {long_mult :a :n} // a -> n*a {- :n 1}} // next else :a // return a }}} -> {def tfac {lambda {:a :n} {if {> :n 0} then {tfac {long_mult :a :n} {- :n 1}} else :a}}} '{tfac 1 100} -> {tfac 1 100} 2) iterative version: '{A.first {S.reduce {{lambda {:a :i} {A.set! 0 {long_mult {A.get 0 :a} {A.get 1 :a}} // a[0] = i*a[0] {A.set! 1 {+ {A.get 1 :a} 1} :a}} // a[1] = a[1]+1 } {A.new 1 2}} // a = [1,2] {S.serie 1 100} }} -> {A.first {S.reduce {{lambda {:a :i} {A.set! 0 {long_mult {A.get 0 :a} {A.get 1 :a}} {A.set! 1 {+ {A.get 1 :a} 1} :a}} } {A.new 1 2}} {S.serie 1 100} }} } _h2 2) fib {prewrap 1) tail-recursive version '{def tfib {lambda {:a :b :n} {if {> :n 0} then {tfib {long_add :a :b} // a -> a+b :a // b -> a {- :n 1}} // next else :a // return a }}} -> {def tfib {lambda {:a :b :n} {if {< :n 1} then :a else {tfib {long_add :a :b} :a {- :n 1}} }}} '{tfib 0 1 100} -> {tfib 0 1 100} 2) iterative version: '{A.last {S.reduce {{lambda {:a :i} {A.set! 1 {long_add {A.get 0 :a} {A.get 1 :a}} // a[1]=a[0]+a[1] {A.set! 0 {A.get 1 :a} :a}} // a[0]=a[1] } {A.new 0 1}} // a=[0,1] {S.serie 1 1000} }} -> {A.last {S.reduce {{lambda {:a :i} {A.set! 1 {long_add {A.get 0 :a} {A.get 1 :a}} {A.set! 0 {A.get 1 :a} :a}} } {A.new 0 1}} {S.serie 1 1000} }} } _p And the iterative version goes beyond the {b stack overflow}, for instance: {prewrap fib(10000) -> 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875 } _p alain marty | 20210403 {style body { background:#444; } #page_frame { border:0; } #page_content { background:transparent; color:#fff; border:0;} .page_menu { background:transparent; color:#fff;} a {color:red} pre { font-size:1.0em; } }
lambdaway v.20211111