An rúndiamhair atá taobh thiar de bharrfheabhsúcháin draíochta Abstract Algorithm a réiteach

Inné, thuairiscigh mé an bhreathnóireacht aisteach gur féidir le feidhmeanna áirithe iad féin a iompar amhail is go raibh castacht dhiúltach acu. Ní gá duit an t-alt sin a léamh roimh an alt seo. I mbeagán focal, tá an λ-téarma f (giotán) = cóip (comp (inc, n, giotán)) níos tapa go neamhshiméadrach ná g (giotán) = comp (inc, n, giotán); ie, iompraíonn cóip (oibríocht O (1) do mhéid seasta) amhail is go raibh castacht O (1 / n) aici, rud a fhágann go rithfeadh an clár níos gasta trí níos mó rudaí a dhéanamh (!?).

Ní hé sin an t-aon toradh casta castachta a bhí agam agus mé ag triail leis an Algartam Teibí. Blianta ó shin, thug mé faoi deara go bhfuil sé in ann cláir a ríomh nach n-oirfeadh i ríomhaire do mhéid na cruinne. Le déanaí, phostáil mé conas is féidir leis oibríocht O (1) N a chur i bhfeidhm N in am O (log (N)) (!?). In ainneoin go raibh freagraí sothuigthe á gcur ar fáil, ba dheacair ciall a bhaint as iompraíochtaí neamhthuisceana den sórt sin.

Tar éis go leor taighde agus roinnt léargas le déanaí, bhuail sé isteach orm sa deireadh. Éiríonn go simplí leis an míniú ar sin ar fad, agus, san alt seo, míneoidh mé a bhfuil ar siúl go cúramach (ní ag magadh an uair seo). Má tá deifir ort, bíodh leisce ort scipeáil chuig an tl; dr ag an deireadh.

1. Is iad na feidhmeanna is fearr is féidir a chomhleá agus iad féin-chumtha

Ar dtús, tosaímid leis an sampla is simplí ar a dtarlaíonn rud suimiúil: arís agus arís eile ní. Déanaimis é a chur i bhfeidhm ar dhá bhealach éagsúla:

Fíor = λt. λf. t Bréagach = λt. λf. f not_a = λb. (b Bréagach Fíor) not_b = λb. λt. λf. (bft)

Mura dtuigeann tú na sainmhínithe sin, is féidir leat léamh faoi ionchóduithe lambda, ach níl sé sin ró-thábhachtach. Anois, conas a dhéanfadh feidhmchláir as a chéile de not_a agus not_b in Absal (cur i bhfeidhm an Algartam Teibí)? Seo cairt:

Coimpléascacht (athscríobh iomlán) maidir le “ní” N a chur i bhfeidhm ar Fíor

Anseo, déantar castacht a thomhas mar athscríobh graf. Ná bíodh imní ort faoi sin, áfach, glac leis go bhfuil an t-am a thógann sé téarma-téarma a reáchtáil comhréireach le líon na n-athscríobh graf. Mar a fheiceann tú, feidhmíonn not_a go líneach, agus feidhmíonn not_b go logartamach. Is difríocht mhór é sin, ar athrú chomh beag sin! Agus tá sé an-neamhthábhachtach freisin, mar níor cheart go mbeifeá in ann N nótaí a chur i bhfeidhm in O (log (N)). Ansin, cén fáth go dtarlaíonn sé sin? Sula bhfreagraíonn tú, déanaimis turgnamh ar dtús. Déanaimis an dá fheidhm a chumadh leo féin agus a ngnáthfhoirmeacha a sheiceáil.

  • norm (not_a.not_a): λb. (b (λt.λf.f) (λt.λf.t) (λt.λf.f) (λt.λf.t))
  • norm (not_b.not_b): λb. λt. λf. (btf)

Suimiúil: a luaithe a bhíonn sé féin-chumtha, fásann not_a níos mó, ach fanann not_b an méid céanna. Cén fáth? Mar gheall ar chomhleádh an fheidhm níos déanaí. Sin an éifeacht chéanna a ligeann do Haskell roinnt pasanna a chasadh thar liosta in aon phas amháin, ag fáil réidh le struchtúir idirmheánacha. Tugann sé sin orainn hipitéis a dhéanamh go bhféadfadh baint a bheith ag an luasghéarú draíochta leis an maoin sin. Déanaimis an hipitéis sin a sheiceáil trí oibriú na léarscáileanna a thástáil ar liostaí:

Nialas = λc. λn. n Cons = λh. λt. λc. λn. ch (tcn) map_a = λf. λl. l (λh. λt. Cons (fh) t) Nia map_b = λf. λl. λc. λn. l (λh. λt. c (fh) t) n liosta = Cons True (Cons False (Cons True (Cons False Nil)))

Anseo, rinneamar é a shainiú arís ar dhá bhealach éagsúla: fiúsanna map_b agus níl map_a. Déanaimis castacht an léarscáil a chur i bhfeidhm arís agus arís eile ar liosta:

Coimpléascacht (athscríobh iomlán) maidir le hamanna “mapa” N a chur i bhfeidhm ar liosta de 4 ghné

Mar a fheiceann tú, tugtar faoi deara an t-iompar céanna anseo: feidhmíonn an leagan a chomhleáíonn go logartamach, agus an leagan nach bhfeidhmíonn go líneach, ag tacú lenár hipitéis. Woa! Ach cén fáth go dtarlódh sé sin?

(Seo an cód chun an turgnamh sin a atáirgeadh agus na cairteacha a ghiniúint.)

2. Exponentiation by squaring = comhdhéanamh trí roinnt

Chun é sin a thuiscint, déanaimis labhairt ar dtús faoi dhíbirt slánuimhir. Más forbróir tú, seans go gcloisfear tú faoi dhíspreagadh trí squaring. Is algartam ársa simplí é atá in ann A ^ B a ríomh i gcéimeanna i bhfad níos lú ná mar a thógfadh sé chun A a iolrú arís agus arís eile, B. Chun ár n-intinn a athnuachan, déanaimis amharc ar an gcaoi a n-oibríonn sé:

# Ríomhaireacht 13 ^ 8 le iolrú arís agus arís eile
13 ^ 2 = 13 * 13 = 169 13 ^ 3 = 13 * 169 = 2197 13 ^ 4 = 13 * 2197 = 28561 13 ^ 5 = 13 * 28561 = 371293 13 ^ 6 = 13 * 371293 = 4826809 13 ^ 7 = 13 * 4826809 = 62748517 13 ^ 8 = 13 * 62748517 = 815730721
# Ríomhaireacht 13 ^ 8 le díbirt trí squaring
13 ^ 2 = 13 * 13 = 169 13 ^ 4 = 169 * 169 = 28561 13 ^ 8 = 28561 * 28561 = 815730721

Mar a fheiceann tú, iolraíonn an chéad chur chuige 13 ceann ar cheann, agus bíonn gá le iolraithe N chun 13 ^ N (am líneach) a bhaint amach, agus déanann an dara ceann an chéad uimhir a chearnú arís agus arís eile, rud a ligeann dó léim ó 13 ^ 1 go 13 ^ 2 go 13 ^ 4 go 13 ^ 8 in iolrú aonair do gach léim (am logartamach). Chun luachanna nach cearnóga foirfe iad a ríomh, ní dhéanann tú ach fo-théarmaí a iolrú, ie, 13 ^ 11 = 13 ^ 8 * 13 ^ 2 * 13 ^ 1.

Néata, ceart? Ach conas atá sé sin ábhartha? Mar gheall ar fhíric nach bhfuil chomh coitianta, maidir le haon fheidhm is féidir a chomhleá le comhdhéanamh, is féidir linn a feidhmchlár arís agus arís eile a ríomh i gcéimeanna O (log (N)) agus an cleas céanna sin á úsáid againn! Déanaimis é a shamhlú freisin:

# Ríomhaireacht nach ^ 8 (t) le cur i bhfeidhm arís agus arís eile
ní ^ 2 (t) = (λb.λf.λt. bft). (λb.λf.λt. bft) = (λb.λf.λt. btf) not ^ 3 (t) = (λb.λf.λt. bft). (λb.λf.λt. btf) = (λb.λf.λt. bft) not ^ 4 (t) = (λb.λf.λt. bft). (λb.λf.λt. bft) = (λb.λf.λt. btf) not ^ 5 (t) = (λb.λf.λt. bft). (λb.λf.λt. btf) = (λb.λf.λt. bft) not ^ 6 (t) = (λb.λf.λt. bft). (λb.λf.λt. bft) = (λb.λf.λt. btf) not ^ 7 (t) = (λb.λf.λt. bft). (λb.λf.λt. btf) = (λb.λf.λt. bft) not ^ 8 (t) = (λb.λf.λt. bft). (λb.λf.λt. bft) = (λb.λf.λt. btf)
# Ríomhaireacht nach ^ 8 (t) le comhdhéanamh trí roinnt
ní ^ 2 (t) = (λb.λf.λt. bft). (λb.λf.λt. bft) = (λb.λf.λt. btf) not ^ 4 (t) = (λb.λf.λt. btf). (λb.λf.λt. btf) = (λb.λf.λt. btf) not ^ 8 (t) = (λb.λf.λt. btf). (λb.λf.λt. btf) = (λb.λf.λt. btf)

Ceart go leor, tá sé sin ró-deacair é a léamh. Cuirimis a n-ainmneacha in ionad lambdas:

# Ríomhaireacht nach ^ 8 (x) le cur i bhfeidhm arís agus arís eile
ní ^ 2 (x) = ní. ní = id ní ^ 3 (x) = ní. id = ní nach ^ 4 (x) = ní. ní = id ní ^ 5 (x) = ní. id = ní ní ^ 6 (x) = ní. ní = id ní ^ 7 (x) = ní. id = ní nach ^ 8 (x) = ní. ní = id
# Ríomhaireacht nach ^ 8 (x) le comhdhéanamh trí roinnt
ní ^ 2 (x) = ní. ní = id ní ^ 4 (x) = id. id = id ní ^ 8 (x) = id. id = id

An bhfeiceann tú é? Tá feidhm ag an gcéad chur chuige ceann ar cheann, agus iarratais N ag teastáil chun an toradh deiridh a bhaint amach (am líneach), agus déanann an dara ceann an fheidhm tosaigh a fhéin-chomhdhéanamh arís agus arís eile, ag léim ó not ^ 2 go not ^ 4 go not ^ 8 agus gan ach ceann amháin comhdhéanamh do gach léim (am logartamach). Is é sin le rá, chomh fada agus a chomhdhéanann féin fiúsanna, is féidir linn feidhmchlár arís agus arís eile a chur i bhfeidhm in am logartamach, agus an cleas céanna taobh thiar den easpónantú á úsáid againn ag squaring!

3. Déanann Absal comhleá runtime

Faraor, agus a fhios againn nach leor an cleas chun halgartaim fusible a bhrostú: teastaíonn teanga fheidhmiúil uainn freisin a bheidh in ann comhleá gearr-ghearrtha a dhéanamh le linn am rith. Maidir le ceann amháin, níl Haskell in ann é sin a dhéanamh le haghaidh feidhmeanna dúchasacha. Mar léiriú, déanaimis “comhdhéanamh trí chur i bhfeidhm” ann:

Tógann an fheidhm seo uimhir n, feidhm f, agus seoltar feidhm nua ar ais a bhaineann f arís agus arís eile le x, n huaire, agus an modh “comhdhéanamh trí roinnt” á húsáid. Mar shampla, déanann (comp (ní, 10, x)) luacháil ar a choibhéis:

Tabhair faoi deara an chaoi nach mbaineann an fheidhm seo 10 n-uaire lena hionchur, cé nach n-úsáideann sí comhdhéanamh ach 3 huaire? Sin an fáth gur chóir go mbeadh sé éifeachtach. Mar sin, cad é castacht comp (nach bhfuil, N, x) i Haskell? Ní logartamach mar a bheimis ag súil leis, ach líneach! Is féidir leat an fíric sin a thástáil tríd an Gist seo a rith. Má athraíonn tú 2 ^ 20 go rud éigin níos airde mar 2 ^ 40, rithfidh sé as cuimhne. Cén fáth? Toisc go bhfuil sé ró leisciúil agus nach ndéanann sé meastóireacht riamh taobh istigh de lambdas, rud a bheadh ​​riachtanach chun na nathanna idirmheánacha sin a chomhleá. Agus, fiú má rinne, níor oibrigh sé fós. Fiosraíonn an post ar leithligh seo an fáth, ag scrúdú samhail meastóireachta Haskell agus JavaScript agus cén fáth nach bhfuil siad barrmhaith.

Anois táimid gar do réiteach ár bhfreagra. Ach, ar dtús, caithfimid labhairt faoi Cruinneanna comhthreomhara; Ciallaíonn mé, laghduithe comhthreomhara. Is é an léargas is mó atá taobh thiar de Absal ná líonta idirghníomhaíochta a úsáid in ionad uiríll théacsúla níos simplí. Is samhail ríofa iad líonta idirghníomhaíochta bunaithe ar ghraif le calafoirt lipéadaithe (ceann acu an “príomhphort”) agus caveat an-aisteach: aon uair a chomhlíontar dhá “phríomhphort”, athscríobhtar na nóid atá ceangailte leo.

Athscríobh rialacha comhcheanglóirí idirghníomhaíochta, cineál líon idirghníomhaíochta

Tá éifeacht an-spéisiúil leis sin: is cuma cén t-ord a athscríobh tú do nóid, fanann líon iomlán na gcéimeanna seasmhach. Dá bhrí sin, má thiomsaíonn tú λ-théarmaí le líonta idirghníomhaíochta, ansin is féidir leat nathanna a laghdú in aon ord: feidhmeanna ar dtús, argóintí ar dtús, fiú go comhthreomhar. Sa deireadh, beidh an saothar léirithe mar an gcéanna!

Is é an cleas, ar ndóigh, ná conas λ-théarmaí a aistriú i gceart chuig líonta idirghníomhaíochta. Faraor, níl aon réiteach air sin a chumhdaíonn na téarmaí uile go héifeachtúil. Ach, i gcás aicme ollmhór díobh (cibé rud a scríobhfá go praiticiúil is dócha), tá bealach simplí galánta ann chun é a dhéanamh: sin an Algartam Teibí. Chun é a mhíniú go gairid, bíonn nód trínártha ar an glan i ngach lambda agus gach feidhm de théarma, agus déantar “nód lucht leanúna” de gach athróg a tharlaíonn arís agus arís eile. Chomh maith leis sin, díríonn príomhphort nód feidhmchláir ar an bport feidhme, agus is é sin an fáth nach féidir fuascailtí a mhacasamhlú riamh.

Má tá tú sáraithe, ná bíodh imní ort. Is é an príomhléargas ná, trí bheith saor chun téarmaí a laghdú i cibé ord is mian leis, go bhfuil Absal in ann a bheith chomh fonnmhar agus is féidir gan aon phionós feidhmíochta, rud a ligeann dó, ina dhiaidh sin, cumadóireacht idirmheánach a chomhleá. Seo go díreach a theastaíonn chun an cleas “comhdhéanamh trí chomhroinnt” a shaothrú. Más mian leat tuiscint níos fearr a bheith agat ar an Algartam Coimrithe, molaim an leabhar seo a léamh, tá sé thar a bheith oideolaíoch. Nó is féidir leat smaoineamh ar an íomhá thíos:

Léiríonn sé meastóireacht ar an téarma (λg. G (g λx. X)) (λh. (Λf. F (f λz. Z)) (h λy. Y)) ar an algartam teibí. Tabhair faoi deara conas is féidir fo-nathanna a roinnt ar roinnt téarmaí, conas is féidir linn meastóireacht a dhéanamh taobh istigh de lambdas gan aon obair dhúblach a chur i mbaol (agus cé go mbeimid fós in ann a bheith leisciúil), agus an chaoi a bhfuil laghdú béite-ama aonair san fhormáid seo comhionann le roinnt béite-laghduithe ar uiríll níos traidisiúnta. Álainn, níl?

Ach cad faoi na rudaí castachta diúltacha?

Déanaimis gach a bhfuil foghlamtha againn go dtí seo a athshlánú. Ar dtús, comhleádh roinnt feidhmeanna λ-calcalas nuair a bhíonn siad féin-chumtha. Le “fiús”, is é atá i gceist agam go bhfanfaidh méid a ngnáthfhoirmeacha seasmhach. Ar an dara dul síos, is féidir na feidhmeanna sin a chur i bhfeidhm N uaireanta le castacht O (log (N)) trí úsáid a bhaint as an straitéis “comhdhéanamh trí roinnt”, fad is féidir leis an teanga óstach fo-nathanna taobh istigh de lambdas a normalú go fonnmhar. Ar an tríú dul síos, tá Absal in ann meastóireacht a dhéanamh ar lambdas taobh istigh, rud a ligeann dó é sin a dhéanamh go díreach, ag cumadh cumadóireachta istigh le linn am rith. Tugann sé sin conclúid loighciúil amháin dúinn: caithfidh cóip a bheith ina chúis le fiús a bhaint as! WOW! An bhféadfadh sé a bheith? Déanaimis an hipitéis sin a thástáil trí ghnáthfhoirmeacha a chuardach!

- Gnáthfhoirm `inc`: λa. λb. λc. λd. (((ac) λe. (b λf. λg. λh. ((m.sh.) λi. (f λj. λk. λl. (((ik) λm. (jm)) l)) h))) d )
- Gnáthfhoirm `inc. inc`: λa. λb. λc. λd. (((a λe. (b λf. λg. λh. ((m.sh.) λi. (f λj. λk. λl. (((ik) λm. (jm)) l)) h)))). (c λf. λg. λh. ((eg) λi. (f λj. λk. λl. (((ik) λm. (jm)) l)) h)) d)
- Gnáthfhoirm `inc. inc. inc`: λa. λb. λc. λd. (((a λe. (c λf. λg. λh. ((m.sh.) λi. (f λj. λk. λl. (((ik) λm. (jm)) l)) h)))). (b λf. λg. λh. (((e λi. (f λj. λk. λl. (((ik) λm. (jm)) l))) λi. (g λj. λk. λl. (((( ik) λm. (jm)) l))) h))) d)
---------------------------------------------- -----------
- Gnáthfhoirm de `chóip. inc`: λa. (((a λb. λc. λd. λe. (d (((b λf. λg. λh. λi. (g (((f λj. λk. λl. λm. (kj)) λj. λk. λl. λm. (Lj)) λj. λk. λl. L))) λf. λg. λh. λi. (H ((f λj. λk. λl. λm. (Kj)) λj. λk. λl. λm. (lj)) λj. λk. λl. l))) λf. λg. λh. h))) λb. λc. λd. λe. (c (((b λf. λg. λh. λi. (h (( (f λj. λk. λl. λm. (kj)) λj. λk. λl. λm. (lj)) λj. λk. λl. l))) λf. λg. λh. λi. (g (((f) λj. λk. λl. λm. (Lj)) λj. λk. λl. λm. (Kj)) λj. λk. λl. L))) λf. λg. λh. H))) λb. λc. λd. d)
- Gnáthfhoirm de `chóip. inc. inc`: λa. (((a λb. λc. λd. λe. (c (((b λf. λg. λh. λi. (h (((f λj. λk. λl. λm. (kj)) λj. λk. λl. λm. (Lj)) λj. λk. λl. L))) λf. λg. λh. λi. (G (((f λj. λk. λl. λm. (Lj)) λj. λk. λl. λm. (kj)) λj. λk. λl. l))) λf. λg. λh. h))) λb. λc. λd. λe. (d (((b λf. λg. λh. λi. (h (( (f λj. λk. λl. λm. (kj)) λj. λk. λl. λm. (lj)) λj. λk. λl. l))) λf. λg. λh. λi. (g (((f) λj. λk. λl. λm. (Lj)) λj. λk. λl. λm. (Kj)) λj. λk. λl. L))) λf. λg. λh. H))) λb. λc. λd. d)
- Gnáthfhoirm de `chóip. inc. inc. inc`: λa. (((a λb. λc. λd. λe. (d (((b λf. λg. λh. λi. (h (((f λj. λk. λl. λm. (kj)) λj. λk. λl. λm. (Lj)) λj. λk. λl. L))) λf. λg. λh. λi. (G (((f λj. λk. λl. λm. (Lj)) λj. λk. λl. λm. (kj)) λj. λk. λl. l))) λf. λg. λh. h))) λb. λc. λd. λe. (c (((b λf. λg. λh. λi. (g (( (f λj. λk. λl. λm. (lj)) λj. λk. λl. λm. (kj)) λj. λk. λl. l))) λf. λg. λh. λi. (h (((f) λj. λk. λl. λm. (Lj)) λj. λk. λl. λm. (Kj)) λj. λk. λl. L))) λf. λg. λh. H))) λb. λc. λd. d)
- Nóta: doimhneacht shocraithe 3 a úsáid chun léirshamhlú níos fearr a dhéanamh

Tá ann! Sin é go díreach a tharlaíonn. Ná bíodh imní ort faoi ábhar na dtéarmaí sin, nílimid ag smaoineamh ach ar a méideanna. Anseo, tá comhdhéanamh inc leis féin beag, ach de réir mar a choinnímid níos mó inc.s i gceangal leis, fásann an gnáthfhoirm níos mó, go líneach. Is é sin le rá, ní chomhleáíonn inc leis féin. Mura gcuirimid ach cóip leis. de réir seicheamh na inc.s, ansin bíonn gnáthfhoirm na feidhme a bhíonn mar thoradh air níos mó, ach fanann sí seasmhach, beag beann ar líon na gcomhdhéanamh. Is é sin le rá, ní dhéanann a fhéin-chomhdhéanamh ach athróga a athrú agus, dá bhrí sin, fiúsanna iad. Ligeann sé sin, ar a uain, an éifeacht “comhdhéanamh trí chomhroinnt” a thosú, rud a fhágann go bhfuil castacht logartamach ag an Nú comhdhéanamh inc. Mothaíonn sé go maith, inc.!

Agus sin é. Réitíodh rúndiamhair. Seo an cód chun an turgnamh seo a mhacasamhlú le Absal (féach mo phost roimhe seo le haghaidh treoracha suiteála).

Is í an cheist dheireanach a bheadh ​​ar feitheamh: cén fáth go bhfuil an chóip ina chúis le fiús? Ach ní deacair é sin a thuiscint. Ar dtús, déanaimis na sainmhínithe ar chóip agus inc a shamhlú:

Anois, déanaimis doimhneacht d = 2 a shocrú agus an méid a thiocfaidh chun cinn nuair a bheidh sé comhdhéanta le cóip a shamhlú:

Éiríonn leis an gcóip a tarraingíodh isteach ann féin, agus beathaíonn sé dornán tógálaithe, a rinne é a athrú go feidhm a mheaitseálann patrún go hiomlán le gach brainse dá ionchur go dtí an doimhneacht is mó, in ionad filleadh go ró-luath nuair nach bhfuil gá le tuilleadh oibre, mar a rinne sé roimh. Tabhair faoi deara conas a cuireadh línte 8-21 ar an dara ceann in ionad líne 16 ar an gcéad chnaip. Is é sin le rá, tháinig inc go bunúsach mar thábla mór sár-aistrithe / cuardaigh in ionad gnáthfheidhm athchúrsach. Is droch-smaoineamh é sin, ach is é an clúdach iomlán seo go díreach a bhí ag teastáil chun go mbeadh an fheidhm in ann comhleá a dhéanamh leis féin. Gan é, ní fhéadfaí na hathróga siombalacha a chuirtear ar ais roimh am i mbrainsí áirithe a laghdú tuilleadh, ag carnadh i dtéarmaí féin-chumtha, rud a fhágann go bhfásfaidh siad níos mó agus níos mó. Nó, mar mhalairt air sin, oireann an patrún breise le féin-scriosadh faoi fhéin-chomhdhéanamh, ag coinneáil corp na feidhme beag.

Conclúid

Bhuel, sin turas go leor. Éiríonn leis go raibh mínithe simplí ag an Algartam Teibí taobh thiar dá thorthaí draíochta. Tá áthas orm go ndearna mé na rudaí sin amach faoi dheireadh, agus buíoch de na Redditors a rinne trácht le léargas agus tuairimíocht; go speisialta, / u / matt-noonan, a luaigh an comhdhéanamh trí chleas a roinnt a chuir na píosaí go léir le chéile i mo chloigeann.

tl; dr

In Absal, an cur i bhfeidhm is fearr is féidir ar theangacha feidhmiúla, déantar é a chur i bhfeidhm arís agus arís eile le huimhreacha eaglaise, a léirítear le feidhmeanna a bhfuil go leor comhroinnte inmheánaigh acu. Mar shampla, léirítear 21 mar:

λf1. λx. lig f2 = f1. f1 in lig f4 = f2. f2 in lig f8 = f4. f4 in lig f16 = f8. f8 in f16 (f4 (f1 x))

Tá an fhormáid sin an-chosúil le “exponentiation by squaring”, algartam clasaiceach atá in ann easpónantú A ^ B in O (log (N)) a ríomh in ionad O (N). Ní leor é sin leis féin chun na feiniméin a mhíniú; i Haskell, mar shampla, ní thugann luasghéarú úsáid as an bhfeidhm sin. Tá Absal, áfach, an-fonnmhar (in ainneoin nach bhfulaingíonn sé moilliú ar bith), rud a fhágann go bhfuil sé in ann gnáthfhoirm idirmheánach f a ríomh. f cumadóireachta, ag comhleá go bunúsach ag am rith. Níl sé sin úsáideach ach nuair a bhíonn fiúsanna ann nuair a bhíonn siad féin-chumtha, ar shlí eile d’fhágfadh fás a ghnáthfhoirm moilliú easpónantúil mar gheall ar an gcostas a bhaineann le téarmaí atá ag éirí níos mó a chóipeáil.

Má chomhleádh f faoi fhéin-chomhdhéanamh, áfach, léiríonn Absal éifeacht “comhdhéanamh trí chomhroinnt”, atá cosúil le “easpónantú trí squaring”, ach amháin le feidhmeanna agus comhdhéanamh in ionad slánuimhreacha agus iolrú. Is é seo a ligeann dó feidhmchláir arís agus arís eile N in am O (log (N)) a ríomh. Ar deireadh, cas amach cóip. déanann inc claochlú ar inc ina feidhm a dhéanann féin-chomhleá, trí shiombailí a charnaíonn lambdas a fhéin-scriosann faoi fhéin-chomhdhéanamh a athsholáthar, agus sin an fáth go bhfuil sé níos gasta go neamhshiméadrach ná inc amháin.

tl; dr tl; dr

Draíocht.