§2.1 Machten
Er zijn drie elementaire operaties tussen getallen.
Optelling +
wat getallen samen telt,
vermenigvuldiging *
wat tellen herhaalt,
en nu dan machtsverheffing met
^
of **
als operator.
Zowel de operatie als het resultaat ervan
noemen we een macht
.
Machtsverheffen herhaalt
vermenigvuldigen
met hetzelfde getal. Dat kan per stap worden gedaan.
Onze macht operator is ^
een dakje
,
superscript notatie is ongeschikt voor de computer input lijn.
- a^1 ?= a
- a^b1 ?= a^b*a == a^1.*a.. :b = a*..a :b
De voorwaardelijke toewijzing ?=
staat hier,
omdat een macht rechts in een reeks elementaire operaties
voorrang krijgt. Bijv. de expressie
a^b^c
betekent a^(b^c)
,
waar de subexpressie b^c
eerst wordt uitgewerkt (tot exponent).
Onze logaritme functie Log
is een inverse van machtsverheffing,
en nog wat weetjes over operaties met machten.
- m^p*m^q = m^pq (m^p)^q = m^(p*q) n^-*n = 1
- m^Log(m,n) = n Log(m,p*q) = Log(m,p)+Log(m,q) Log(m,n)*Log(k,m) = Log(k,n)
Ster operaties *..
evalueren we hier strikt `=
vanaf links.
Daar zijn geen haakjes bij nodig
of vergelijkende precedentie regels.
Alleen een rechter operatie zonder plus,
die volgt na een operatie met pop plus,
wordt met voorrang geholpen.
Het aantal sterren tellen we in deze evaluatie af naar links,
tot we op nul *{0}
uitkomen en de operanten ac
natuurlijk
optellen.
Een l-r definitie voor machten
met **
twee popsterren.
- a**b1 `= a+*a**b (popster)
- c+*a+* `= a*c+* (popschuif)
- c+*a**1 = a*c (ontpop)
We gebruiken een popster
om een macht af te schermen van zijn uitwerking,
die links plaats vindt.
Het plus teken van +*
fungeert als haakje, maar is tijdelijk
en verdwijnt als deze als ster operatie opschuift
voor een nieuw popster haakje.
# Experiment 2.1
Ontwerp een Superplus
systeem.
Pas de regels in volgorde toe, zodat
c>1
voor de eind iterator en
b>0
en
c>0
in de recursie.
- a+b = ab
- a+{c}1 = a
- a+{c1}b1 = a+{c}a+{c1}b
Als we hierbij prioriteit
tegelijk met subexpressies overboord gooien,
en +..
operatoren puur l-r evalueren, werkt dat dan?
Ja en snel, twee plussen ++
herhaalt de verdubbeling van a
.
a++b2 = a+a++b1 = aa++b1 = aaaa++b == a.*2..++1 :b1 = a*2^b1
Een post operatie \^
plaatst na uitwerking van de voorafgaande operatie
een extra exponent bovenop de hoogste suboperant daarvan.
Post operatie \*
vermenigvuldigt deze hoogste exponent dan wel superexponent
(met prioriteit zodra deze er is).
We plaatsen de post backslash rechts en draaien
de operanten niet om, zoals bij de pop plus links van de operatie.
We vergelijken superplussen met ^..
supermachten, die in
§2.2
een historisch overzicht krijgen.
De expressie links van ≈>
is maar weinig (insignificant) groter dan die rechts.
- a1+++b3 = a1++a1+++b2 = a1*2^a+++b2 ≈> 2^(a*2^a)+++b1 ≈> 2^2^2^a1+++b ≈≈ 2^..a1+++1 :b2 = 2^^b2\^a1 ≈ a^^b3
- a1+{c2}b2 = a1+{c1}a1+{c2}b1 ≈ a^{c}a1+{c2}b1 ≈ a^{c}a^{c}a1+{c2}b ≈≈ a^{c}..a1 :b1 = a^{c1}b1\^{c}a1 ≈> a^{c1}b2
Door twee tekens,
de 1
en +
plus,
te gebruiken krijgen we supergrote getallen.
Ook al laten we de enkele tekens domweg vallen,
in de initiële regels.
Bijv. 11+++++111
≈
2^^^^3
=
2^^65536.
Omdat a+{c}b
<≈
a*{c}b
zijn de recursies in de functies van superplussen
D(a,b1,c1)
=
D(D(a,a,c),b,c1)
en van de supermachten
F(a,b1,c1)
=
F(a,F(a,b,c1),c)
die we later bespreken, ongeveer even snel.
Ontwerp nu een hybride functie met meervoudige recursie
op twee posities. Noem dit de Excalibur
functie:
het tweesnijdend zwaard.
- E(a,b,1) = E(a,b) = ab
- E(a,1,c) = a
- E(a,b1,c1) = E(E(a,a,c),E(a,b,c1),c)
Rozsa Péter stelt2 dat recursie in meerdere variabelen tegelijk niet significant sneller gaat, en dit willen we testen.
- E(a,b1,2) = E(aa,E(a,b,2)) == E(aa,..a..) :b: = a*2*b+a
- E(a1,b1,3) ≈> E(a^2*2,E(a,b,3),2) ≈> aa^2*E(a,b,3) ≈≈ aa^2*..a :b = aa^bb*a
- E(a1,b1,4) ≈> E(aa^aa,E(a1,b,4),3) ≈> aa^(a*3*E(a1,b,4)) ≈≈ a1^..(a*a*3) :b>0 ≈> a1^^b1\^2
- E(a,b1,5) ≈> E(a^^a,E(a,b,5),4) ≈> a^^(a+E(a,b,5)-) ≈≈ a^^..aa- :b>0 <≈ a^^^b1\*2
- a^{c}b < E(a,b,c2) <≈ a^{c}b\*2 < aa^{c}b
We verwachten dat hogere expressies E
als de bij c=5
berekende
zullen verlopen, en niet verder zakken richting F
.
In ieder geval voegt de extra recursie hier weinig toe,
al is argument a
ongeveer verdubbeld.
Misschien als we de extra stap E
in stap F
nesten, dat dat hogerop groter uitpakt?
- G(a,b,1) = G(a,b) = ab
- G(a,1,c) = a
- G(a,b1,c1) = G(a,G(G(a,a,c),b,c1),c)
Als we onze Griffioen
functie uitwerken,
dan neemt supermacht c
1
toe,
vergeleken met E
of superplussen.
In het vervolg telt het tweede argument bijna als b*2
,
wat te verwachten viel door het dubbele nesten in de recursie stap.
- G(a,b2,2) = a+G(aa,b1,2) = a*3+G(a*4,b,2) == a*(2^b2)- ≈ 2^b2
- G(a,b2,3) ≈ 2^G(2^a,b1,3) = 2^2^G(2^2^a,b,3) == 2^^b1\^2^^b1\^a = 2^^bb2\^a ≈ 2^^bb4
- G(a,b1,4) ≈ 2^^G(2^^aa,b,4) == 2^^..2^^..aa :b :b = 2^^^bb\^^aa ≈ 2^^^bb2
- G(a,b1,c1) ≈ 2^{c}bb\^{c-}aa ≈ a^{c}bb1 ≈ 2^{c}bb2
Omdat argument c
ongemoeid blijft,
draagt het nesten van meerdere subexpressies
niet wezenlijk bij aan het maken van grotere getallen,
als die recursies op zich al supermachten
opleveren.∴
Een serie gelijke operaties komt in de evaluatie
van super popster operaties nooit voor.
We zien duo's van ster en popster,
met een naar links afnemend aantal sterren.
Als we een pop operatie links vóór de macht plaatsen,
dan zal deze opereren op de hoogste factor,
die steeds naar rechts schuift.
Eerst een simpel voorbeeld, dan de algemene formule.
- 1+2**3 = 1+2+*2**2 = 3+*2**2 = 3+*2+*2**1 = 2*3+*2**1 = 2+2*2+*2**1 = 4+2*1+*2**1 = 6+*2**1 = 2*6 == 12.
- p+*{q}a*{c1}b1 = a*{q}p+*{c}a*{c1}b = a^{c}b1\*{q}p
Bij rekenen met sterren,
moeten we soms haakjes toepassen.
Maar hier gaat het erom één ster operatie
in stappen uit te werken.
Een popster
+*{c}
stelt zijn operatie niet alleen uit,
maar draait de operanten daarna ook om.
Dit popschuiven
blijft gelijk in geval +*
want vermenigvuldigen is commutatief,
maar bij supermachten maakt omdraaien groot verschil.
Popschuiven is nodig vanaf +**
bij dubbele machten.
Die ontstaan bij het uitwerken van tetraties ***
in enkele stappen =
zoals we dat hieronder doen,
tot de herhaling ==
ervan duidelijk is.
3***3 = 3+**3***2 = 3+**3+**3***1 = 3**3+**3***1 3**3 = 3+*3**2 = 3+*3+*3**1 = 3*3+*3**1 3*3 = 3+3*2 = 3+3+3*1 = 6+3*1 = 9 (ontpopt) 3**3 = 9+*3**1 = 3*9 (ontpopt) == 27. 3***3 = 27+**3***1 = 3**27 (ontpopt) = 3+*3**26 == 9+*3**25 = 9+*3+*3**24 (popster) = 3*9+*3**24 (popschuif) == 27+*3**24 === 7625597484987.
Stel dat we de regel voor popschuiven
vervangen door popruimen
,
dus plus +
eliminatie
zonder dat er operanten verwisseld worden.
Dan blijven hekmachten
#..
ver achter op
*..
supersterren.
Hierboven zou
27##3
omdat (3^3)^3
=
3^(3*3)
=
3^9
al een factor 3^18
schelen.
Hoe klein is dan 4####4
in vergelijking en hoe groot is 4****4
of gaat dat te ver voor telbare hekmachten…?
Recursie met k
variabelen
leidt niet buiten de klasse van de primitief recursieve functies
,
p.75 in Rozsa Péter
"Recursive Functions" 1967, 1950.