Friday 26 August 2016

Endless Exponentiation

endless iteror #4

Exponentiation

Frances K*, 2016

Learn to create ever bigger numbers
in an article series on site and blog,
dedicated to Chelsea Manning hero.

© Kreative commons

#4 Exponentiation

We reduce various powers step by step to series of multiplications. Star powers will be supported by pop marks instead of brackets.

4.1 Multiple repetitions

The concept of repeating a repetition operation, which defines exponentiation, is easily confused with the double repetition of a number, which equals two multiplications.
If number n is a length, and you multiply that once for a plane, or twice to measure a volume, then exponentiation sizes up to any number of dimensions.

To multiply a number by itself n*n is a square n2 or 2nd power, which we notate in the formats:
n^2 or n**2 or 2**n or n**2
Next multiplication n*n*n forms a cube n3 or 3d power:
n^3 or n**3 or 3**n or n**3
These formats depend on the method of evaluation to apply, and sometimes we may switch =: between them.

In a mixed context the operand position should be clear from the code alone, not the colours. We delimit a left evaluated operation by a plus + or pluses ++ at the top. And strictly, subspace prefix + is defined for right iterators, and prefix ++ indicates left iterators.

To repeatedly multiply a number by itself is called exponentiation or powers nr in general. A command line expression doesn't allow superscripts, but we automate powers in four formats:

n^r or n**r or
++r**n or +n**r

In each format a different method reduces through suboperations to number. We will explain them in historical order.

Then little Joey, the US treasury, astronomers, and mighty Joe in the multiverse, can create @ll the large numbers they need.

10^3 = 10*10^2 = 10*10*10^1
     = 10*10*10 = 1000

1000**5 = (10**3)**5 = 10**3*5
     = 10**15 = 1000000000000000
        =: 1,000,000,000,000,000

++2**+2***10 = ++2**10**+1***10
 ++2**10**10 = ++100**10
   =: 10^100 =: 1E100    googol

+10**(10**100)
    =: +2+*10***3
     = +10**2+*10***2
     = +10**100+*10***1
          =: 10^10^100
          =: EEE2     googolplex

The blue star ** is so powerful: right iterator, left evaluation, that it only accepts single operation input. The red star ** with left iterator and left evaluation subspace, is our all-round red riding hood.

4.2 Caret powers

A caret ^ is the ascii sign for powers or exponentiation, but programmers may use a double star ** in a similar way.
The usual ^ powers have precedence over * multiplication.

Define exponentiation by a single multiplication step, then iterate == over that to form a series of multilications.
To show examples, click @t the board.

@

n^(r+1) = n*n^r
       == n*..n^1 :r
        = n*..n :r

5^(2+1) = 5*5^2
       == 5*..5^1 :2
        = 5*..5 :2

5^(2+1) = 5*5^2
       == 5*5*5^1
        = 5*5*5 = 125

4^(3+1) = 4*4^3
       == 4*..4^1 :3
        = 4*..4 :3

4^(3+1) = 4*4^3
       == 4*4*4*4^1
        = 4*4*4*4 = 256

2^(9+1) = 2*2^9
       == 2*..2^1 :9
        = 2*..2 :9

2^(9+1) = 2*2^9
 == 2*2*2*2*2*2*2*2*2*2^1
  = 2*2*2*2*2*2*2*2*2*2 = 1024

We don't follow the custom from physics, where you multiply without an operator sign, as if this empty ^{0} does nothing.
We feel that addition of unary numbers mn is the true void operator, first comes multiplication, and next recursions are enumerated from there: counting *{s} stars.

Operators with multiple carets ^.. evolved from the arrow functions .. invented by Donald Knuth, who is an expert in algorithms for computers. Knuth's superexponential operators are also called up-arrows, but nowadays only the arrowhead or caret remains.
In a short article in 1976 Knuth invented his arrows to show that finite numbers can get extremely large, and therefore we should consider them just as interesting as infinite numbers. Quite a statement from a man who injected infinity in the real field with his surreal numbers.

Multiple carets ^.. are ruled by right majority precedence. So major operations with more carets are reduced to number first, and adjacent equal operators are worked away from the right.
For variety between operators and to save on brackets, you can use them together and evaluate majority carets before minority stars.

4.3 Minority star powers

Now describe star operations *.. ruled by minority precedence, where lesser stars are reduced to number first.

a**b*c = a**(b*c)
a*b**c = (a*b)**c

Because zero stars *{0} is a virtual operator for direct addition, it is consistent to evaluate smaller operators sooner.

In this section we apply right minority precedence. So operations with equal stars are worked out rtl (from right to left).

a**b**c = a**(b**c)

We paint right minority stars black by default (with a blue accent inside brackets).

Evaluating these operations stepwise, a preceding suboperation is spawned on the right, and this immediately gets precedence. We work it out on top, before completing the whole subtower.
For example the power n**r has to wait inactivated until its first suboperation n*n produces a number p, that then becomes the iterator for a new suboperation n*p etc.

But we have to take care to shield off the iterator r in the original operation from the resulting p of the suboperations.
To separate operations we introduce pop marks + that postpone operations, and function like temporary brackets. A pop +* waits and separates the sub from the super space.

Define minority star exponentiation ** by its multiplication * step, using left pops +* that express a factor on top.

@

n**r1 = n**r+*n
n**r1+*p = n**r+*n*p
n**1+*p = n*p

3**111 = 3**11+*3
3**11+*3 = 3**1+*3*3
3**1+*9 = 3*9 = 27
2**6 = 2**5+*2
2**3+*8 = 2**2+*2*8
2**1+*32 = 2*32 = 64

The postponed operation +* with its iterator p waits for the next factor n to come free. Then n*p shifts on top and has precedence.

We use a left pop +* to shield the original exponent from the suboperations issued on the right.
By introducing, shifting and eliminating pops we can evaluate superexponents using a minimum of signs (without brackets).

4.4 Leftist star powers

In expressions like a*b**c**d*e the rule of right minority precedence champions the largest numbers. But because exponents matter most, the results of straight rtl top down evaluation are almost as big.

a*(b^(c^(d*e))) <≈ (a*b)^(c^(d*e))

Now we'd like to evaluate operators without the use of precedence rules. Operators can become so big and complex that it's not so straightforward to compare them in size anymore.
Also we'd rather do without inner expressions in (group) brackets.

The alternative is to scan expressions ltr, and to apply rewrite rules strictly from left to right. This way we won't meet difficult precedence choices during evaluation.
Our leftist powers r**n are quite revolutionary: with the usual operands reversed and suboperations issued on the left.

Operators are painted red, when the iterator operand is placed left. But if operand position doesn't matter, because iterator and item happen to be n**n equal, or for commutative r*n multiplication, we let stars have the normal colour.

Define red star powers by working out := multiplications pi*n on the left. Click @ for examples.

@

2r**n = n*+1r**n
      = p1*n*+r**n where p1=n
   := p2*+r**n    where p2=n*n
   == pr1*+1**n  where pr1=n..*n r:
    = pr1*n
   := pr2 = n.*n.. :r1 for  r0
& 1**n = n = 1*n
<=> r**n = 1.*n.. :r for  r>0

11111**2 = 2*+1111**2
     = 2*2*+111**2
    := 4*+111**2
    == 16*+1**2
     = 16*2
    := 32

6**3 = 3*+5**3
     = 3*3*+4**3
    := 9*+4**3
    == 243*+1**3
     = 243*3
    := 729

8**8 = 8*+7**8
    := 64*+6**8
    == 2097152*+1**8
    := 16777216
     1.7E7

Moving ltr a suboperation is reduced to number first, before the next is issued. We use right pops *+ to keep the subroutines separated from the original iterator.
Semi-permeable bracketing by pops is crucial in the event a subtotal := pi is ready and the superoperation r**n is decremented again. The formerly postponed operator then shifts and becomes active with a new item *n to repeat, and the next pop *+ is put in place to stand guard.

Berlin 1910, lady mason on a ladder high above a smokey city

Friday 19 August 2016

Endless Repetition

endless iteror #3

Repetition

Frances K*, 2016

Learn to create ever bigger numbers
in an article series on site and blog,
dedicated to Chelsea Manning hero.

© Kreative commons

#3 Repetition

We grab the tools to work out repetitions, and define multiplication by a series of empty additions.

3.1 Word reps

In programming languages Regular Expressions are used to scan text and find words that match a regex. We have similar tools to describe repetition of any subexpression.

Repeat a sign or variable either with a regex quantifier {r} inside an expression, or on the dots .. with a rep :r right outside.

@

a*{c}b 
= a*..b *:c
v{n1} 
= v{n}v  
= v.. :n1
a*{1}b 
= a*b
= a*..b *:1
v{1} 
= v{0}v  
= v
= v.. :1
a*{2}b 
= a**b
= a*..b *:2
v{2} 
= v{1}v  
= vv
= v.. :2
a*{3}b
= a***b
= a*..b *:3
v{3} 
= v{2}v  
= vvv
= v.. :3
a*{4}b 
= a****b
= a*..b *:4
v{4} 
= v{3}v  
= vvvv
= v.. :4
a*{5}b 
= a*****b
= a*..b *:5
v{5} 
= v{4}v 
= vvvvv
= v.. :5

Please click the boards for examples!
The yellow sidebar highlights the use of unary constants (not digits) and natural addition.

To select a word W by dots, a single dot can . mark the left side of W, while double dots .. mark it on the right.

@

X.V..Z :0 
= XZ
W..Y :0 = Y
X.V..Z :1 
= XVZ
W..Y :1 = WY
X.V..Z :2 
= XVVZ
W..Y :2 = WWY
X.V..Z :3 
= XVVVZ
W..Y :3 = WWWY
X.V..Z :4 
= XVVVVZ
W..Y :4 
= WWWWY
X.V..Z :5 
= XVVVVVZ
W..Y :5 
= WWWWWYX.V..Z :6 
= XVVVVVVZ
W..Y :6 
= WWWWWWY
X.V..Z :7 
= XVVVVVVVZ
W..Y :7 
= WWWWWWWY

In case right dots have no left dot(s) preceding and there is no word specified W:n in the rep, the repeated word starts at the left of the expression (after the space).

For a subexpression that is expanded from the middle to the left and right at once, we use a two-sided rep.

@

Vi(..X..)Wi :n:
Vi(..X..)Wi :0: 
= X
Vi(..X..)Wi :1: 
= V1(X)W1
Vi(..X..)Wi :2: 
= V2(V1(X)W1)W2
Vi(..X..)Wi :3:
    = V3(V2(V1(X)W1)W2)W3
Vi(..X..)Wi :4:
    = V4(V3(V2(V1(X)W1)W2)W3)W4

Click to show that iteration variable i increments at every step of the repetition. We can also let a secondary iterator j increment for each i all over again in a nested loop.

Our repex notation allows us to iterate over rewrite rules that are defined in single steps. It's an intuitive tool, you can pick it up as we go.

3.2 Multiplication

A common way to multiply two numbers r×n is to take r times the number n and add them together.
Here the item n is put left in the star multiplication n*r and repeated by the iterator r on the right.

When we concatenate unary numbers n.. the multiplication product is directly given. Concatenation works by natural addition, which is the initial superstar operation with zero *{0} stars.

We define multiplication by its addition step, that is trivially selected on the left or right of its product.

@

n*r1 
= n.. :r1 
= n.n.. :r
     = n(n*r) 
= n+n*r
n*3
= n.. :111
= n+n*11
    = n+n+n*1 
= n+n+n
2*3 
= 11.. :111
= 11+11+11
    = 1111+11 
= 111111 = 6n*4
= n+n*111
= n+n+n*11
    = n+n+n+n*1 
= n+n+n+n
2*4 
= 11.. :1111
= 11+11+11+11
    = 11111111 = 8

We already made two choices for evaluation here:
• to place the iterator that counts off steps on the right. The operands have the same order as with exponentiation.
• to derive the suboperation of addition on the left. Generally we scan expressions ltr (left to right) and reduce free suboperations first.

So we add unary numbers directly on the left, while multiplication is kept separated from the growing result by a single postponed + plus.
Or you can leave the + steps to work out later from either side.

Multiplication n*r = r×n is commutative, which means the factors (number item and iterator) can be reversed.
Show examples of stepwise multiplication of: three hands... eight pairs.. nine ones.

@

3×5 = 2×5+5 = 1×5+5+5
    = 5+5+5 = 10+5 = 15

5*3 = 5+5*2 = 55+5*1
    = 555 = 111111111111111
8×2 = 7×2+2
   == 1×2+2+2+2+2+2+2+2
    = 2+2+2+2+2+2+2+2 := 16

2*8 = 2+2*7 = 22+2*6
   == 2222222+2*1
    = 1111111111111111
9×1 = 8×1+1
   == 1×1+1+1+1+1+1+1+1+1
    = 1+1+1+1+1+1+1+1+1 := 9

1*9 = 1+1*8 = 11+1*7
   == 11111111+1*1
    = 111111111

At the final iteration the identity operation is dropped, so the item operand is left over. Either remove and finish the remaining additions, or remove pop + and *1 and return the result.


+ Advanced System

Without direct repetition we must protect a multiplication from its own stepwise evaluation. The single pop + plus, that we put in between, works the same as the old plus: it postpones addition.

n*r2 = n+n*r1
     = n+n+n*r = nn+n*r

Our multiplication rule inserts an addition n+ on the left. At next steps n+ the former addition shifts left and drops its plus, which adds n to the subtotal.
Generally we introduce a new pop and eliminate the plus from the former pop to activate that operation in one go. For each superoperation there is one suboperation kept waiting.

So we can multiply stepwise without inconsistency. But to allow the old addition + gives some pain. Then we should use a double plus ++ to set apart the evaluation subspace on the outside (far left).
Surely in big number arithmetic, we may require the use of brackets m*(n**r) to append lower operations under minority precedence. And deprecate the m+n**r legacy plus.

Berlin 1910, lady mason on a ladder high above a smokey city

Friday 12 August 2016

Endless Numeration

endless iteror #2

Numeration

Frances K*, 2016

Learn to create ever bigger numbers
in an article series on site and blog,
dedicated to Chelsea Manning hero.

© Kreative commons

#2 Numeration

We will unravel how decimal notation works, see how large numbers are handled in history, and explore the boundaries of mathematics.

2.1 Radix notation

The numbers you use daily are in the decimal system. This is a type of radix notation with number base 10 called ten. Although in any radix its base is written as one zero 10.
Here we show numbers in decimal base on an orange background.

You've forgotten (internalized) how this actually works, it's complicated.
The base determines a set of digits in the range 0d<10 to multiply the powers of the base with and add that in series.
This way a word composed of digits equals a unique number n.

Show the popular radices, both in decimal notation (orange) and by simple counting of ones (yellow).

@

 2 =: 11  binary
     {0,1}
 8 =: 11111111  octal
     {0,1,2,3,4,5,6,7}
10 =: 1111111111  decimal base
     {0,1,2,3,4,5,6,7,8,9}
16 =: 1111111111111111  hexadecimal
     {0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f}

We use the sign =: to change between formats.
Click @ to put the digits of each radix on the board.

After you agree on a base, apply repeated multiplication to it. Index each position p by a radix power, starting right with 10^0 = 1 and 10^1 = 10 and put larger powers 10^p on the left (Arabic writing direction).

On each numeral place you can write a digit, that multiplies its radix' power. Then add up that series to get your number, as below.

@

2016 = 1*6+
      10*1+
    10^2*0+
    10^3*2    in base 10
2015 = 1*7+
       8*3+
     8^2*7+
     8^3*3  =: 3737  in base 8
2020 = 1*0+
       2*0+
     2^2*1+
     2^3*0+
     2^4*0+
     2^5*1+
     2^6*1+
     2^7*1+
     2^8*1+    in base 2
     2^9*1+
    2^10*1  =: 11111100100
2018 = 1*2+
      16*14+
    16^2*7 
          =: 7e2  in base 16

Click @ to represent year numbers in different bases.
Or input your own...
in and

 

Radix notation is optimal, because we can uniquely express all natural numbers up to any n within a minimum word space. Any other system with a set of characters of radix size will do worse.

This goes for all natural number bases, but real bases are possible too. Try them in the above App: number 10 in base pi for example.
Radices below 2 show increasing overlap as they approach the lower limit of 1, A growing proportion of their digit series expresses the same numbers. So radices in the range (1,2) could model the overlap produced by arithmetical systems with a basic number.

2.2 Trends in history

The mumbo-jumbo of radix notation soon became automated, else society would now be crippled. What luck that children in the ages before social media were able to learn their elementary operations in decimals. We stand on the shoulders of midgets, as well as giants!

The ancient Egyptians had eight numeral hieroglyphs for the powers of ten up to 10000000 that were directly added in any position to depict numbers and baffle the crowd.
The Romans some MDCLXVI years ago had just those seven letters to work with. Yet the digit concept was already present in speech. D our 500 was quingenti in latin, and 8000 horses octo milia equorum.

The left position of decimal digits is most important. But powers of ten elude the human psyche after a few 1000000000 billion.
Bankers who believe Reaganomics will last, choose to ignore the impact of compound interest and the large debt that produces.
Any growth must stop somewhere, but exponential growth rapidly becomes unsustainable.

For example. If a family of two keeps growing at a general annual rate of 1.1% for 2016 years, it will be larger than the current world population. Enter that on a calculator.
2*1.011^2016 7.6E9
Exponent E9 in scientific notation means that you multiply the decimal factor on its left by *10^9 to get the number, or often an approximation.

A percentage sign % is equivalent to an exponent E-2 on the factor. Multiply the current quantity with that number to get the increase. Add the increase to the quantity, to get the next total.

2.3 Physical limits

Radix notation seems more economical than unary notation, but the extra digit signs employed for number input/output do not help the operations in the throughput. If your goal is to generate extreme numbers, without regard for the unnumbered gaps in between: then using just the character 1 is most frugal, an easy win.

Take the tetration 10^^r1 for example. A unary number 1.. is written in exactly that many places. In radix notation this space is a power of 10 smaller, that is 10^^r digit places.

This reduction in word size is sufficient to express only the simplest tetrations, given the resources of our physical universe.

@

3^^3 = 3^3^3 = 3^27
    =: 111**111111111111111111111111111
     = 7625597484987
     8E12
4^^3 = 4^4^4 = 4^256
     = 10^(log(4)*256)
     10^154.13
     1E154    exponential notation
2^^5 = 2^2^2^2^2 = 2^65536
     = 10^(log(2)*65536)
     10^19728
     E2E4   double exponential notation
3^^4 = 3^7625597484987
     = 10^(log(3)*8E12)
     E4E12
     EEE1    multi-exponential notation

Basically, a power of 10 less subtracts 1 from the tetration iterator.
But even in exponential notation, to approximate moderate input size tetrations, your output becomes too long. Worse is, by reducing your system's precision most numbers will escape the net.

Because we are physical beings we cannot uniquely express the majority of the numbers in the arithmetical sea between the scattered islands of tetration. Even with the help of computers we can only point out a small portion of these illusive numbers in the rather random choice of systems we can make.

According to Seth Lloyd the universe as a computer has at most 10^90 qubits, less than 2^300 binary places. Then the radix representation of tetrations like 4^^4 and 2^^6 by far defeats any known physical data capacity.

The human mind can envision even larger constructs: check out the ancient record 10^^(10^(5*2^120)) in buddhist poetry.
Moving higher, we can still contemplate the strength of our rules, but the big numbers they produce lie wholly beyond imagination…

Berlin 1910, lady mason on a ladder high above a smokey city