mxtlrr / treng

Hyperoperation engine with it's own homebrew big number library.

treng

Treng is an engine for performing hyperoperations, like tetration, pentation, and so on and for forth. It comes with its own small library for handling big numbers, see lib/

What's Tetration?

Tetration is repeated exponentiation, for example $a\uparrow\uparrow{n}$ means $a^{\cdot^{\cdot^{a}}}$, where $n$ copies of $a$ are iterated via exponentiation, for example:

Tetration	Value
$2\uparrow\uparrow1$	1
$2\uparrow\uparrow2$	4
$2\uparrow\uparrow3$	16
$2\uparrow\uparrow4$	65536
$2\uparrow\uparrow5$	$2\cdot10^{19728}$

Usage

Run src/treng.js, there are a few functions that you can use, see the table below:

Function syntax	What it does
f(a,n)	$a\uparrow\uparrow{n}$
g(a,n)	$a\uparrow\uparrow\uparrow{n}$
h(a,n)	$a\uparrow\uparrow\uparrow\uparrow{n}$

treng's Issues

Super slow -- probable rewrite?

Yeah. Even though treng has gone through a rewrite from C++ to JavaScript, the JavaScript rewrite is actually slower!

Computing Function	C++ Time	JavaScript Time
$f(2,4)$	~0.2-0.4s	30s - 3 min
$f(2,5)$	~0.6-0.8s	1-4 min
$f(2,6)$	N/A	>1 hr

Obviously, the data shows that JS may not be the perfect language for this. However, this also may be due to unoptimized functions (#1), but it also may be that string operations where the length of the string $n$ is $> 10^{50}$ digits. This issue is only here to document a potential rewrite / optimizations of other functions that do not fit into pre-existing issues.

`Number::toInt()` fails if number is greater than `18446744073709551615`

Number::toInt() looks like this:

long long unsigned int Number::toInt(){
  return std::stoull(this->toString());
}

This function fails once long long unsigned int reaches it's maximum value, which is 18,446,744,073,709,551,615.
For stuff like $2\uparrow\uparrow6$, this is unacceptable!

What can we do to fix this?

Rewrite toInt to support huge numbers (maybe a vector?)

Optimize `pow(a,b)`

Currently, for example, computing 3^(2^32) takes over 9 minutes just to get to
3^500000.

What can we do to fix this?

1. Split up exponents, for example:

$$ a^n = \prod_{k=1}^{t} a^t $$

(note that here, $t$ is the biggest whole number such that $a/t$.)

2. Store known exponents in a table
   i. If we have already computed the value of the exponent, we store the result in a table so we don't have to compute it again
   ii. If the exponent is something basic like n^2 or n^3, we can store the value of n^2/n^3 in a table so we don't spend computing power.