Implementation of Level-Index Arithmetic for Very Large Numbers
Author
Swastik Banerjee
Title
Implementation of Level-Index Arithmetic for Very Large Numbers
Description
To represent extremely large real numbers, e.g., Tetrational numbers or huge Power Towers, in the ordinary level-index arithmetic format in Mathematica to virtually abolish the problem of overflow, and add support for this new format in many of the usual mathematical operations such as +, *, ^ etc.
Category
Essays, Posts & Presentations
Keywords
numerical analysis, computer arithmetic, level-index arithmetic, overflow, underflow, exponentiation, tetration, power tower
URL
http://www.notebookarchive.org/2020-07-6i9f1t4/
DOI
https://notebookarchive.org/2020-07-6i9f1t4
Date Added
2020-07-14
Date Last Modified
2020-07-14
File Size
114.42 kilobytes
Supplements
Rights
Redistribution rights reserved
Download
Open in Wolfram Cloud
WOLFRAM SUMMER SCHOOL 2020
Implementation of Level-Index Arithmetic for Very Large Numbers
Implementation of Level-Index Arithmetic for Very Large Numbers
SWASTIK BANERJEE
SRM INSTITUTE OF SCIENCE AND TECHNOLOGY, CHENNAI
To represent extremely large real numbers, e.g., Tetrational numbers or huge Power Towers, in the ordinary level-index arithmetic format. Floating-point arithmetic is inadequate to represent these kinds of large numbers, as they are much bigger than the largest real number that can be represented in the Wolfram Language, and hence suffers the problem of overflow. This project introduces a new large number format in Mathematica to virtually abolish the problem of overflow, and adds support for this new format in many of the usual mathematical operations such as +, *, ^ etc.
Try Overflowing Mathematica Ever Again !!
Introduction to Level-Index Arithmetic
Introduction to Level-Index Arithmetic
In the field of scientific computation generally and especially in experimental computing which is often at the heart of simulation and modeling problems, the availability of a robust system of arithmetic offers many advantages. Many such computational problems are prone to failure due to overflow or underflow or to a lack of advance knowledge of a suitable scaling for the problem.
For example, if we wanted to compute the following, Mathematica would throw an Overflow error:
In[]:=
888
88
8
1024
48
128
Out[]=
Overflow[]<Overflow[]
The use of a computer arithmetic system which is free of these drawbacks would clearly alleviate any such difficulties.
One such arithmetic is the introduced by Clenshaw and Olver in 1984.
The idea of the level - index system is to represent a non - negative X as
The use of a computer arithmetic system which is free of these drawbacks would clearly alleviate any such difficulties.
One such arithmetic is the introduced by Clenshaw and Olver
1
The idea of the level - index system is to represent a non - negative X as
X=
f
...
where 0 f 1 and the process of exponentiation is performed l times, with l ≥ 0 .
l and f are the level and index of X respectively.
≤
≤
l and f are the level and index of X respectively.
For example, X = 1234567 =
0.9711308
Level-index Arithmetic is closed under the four basic arithmetic operations (apart from division by zero, of course) and is therefore free of overflow.The arithmetic system allows very large numbers which may not be representable in a conventional floating-point system to be used during interim computation while still returning meaningful results.
Level-index Arithmetic is closed under the four basic arithmetic operations (apart from division by zero, of course) and is therefore free of overflow.The arithmetic system allows very large numbers which may not be representable in a conventional floating-point system to be used during interim computation while still returning meaningful results.
Goal
Goal
The goal of my project was to implement Level-index Arithmetic using Mathematica, so that operations involving huge numbers could be done in the future using the Wolfram Language without the general problem of overflow, e.g., an operation like below:
In[]:=
LevelIndexArithmetic+//FromLIO
23
64
89
233
69
50000
888
88
8
222222
22222
2222
222
22
2
Out[]=
0.209919
10
10
10
10
10
10
10
10
Research and Implementation
Research and Implementation
The implementation involved careful study of various research papers written by Clenshaw, Olver, Turner and Lozier ,and inspecting source codes of other open-source calculators currently in the market that can compute mathematical operations involving fairly large numbers upto a certain degree of precision. However, due to huge approximations made in almost all of the existing implemented algorithms, several issues arose out of them in terms of precision and correct results, and a real need to do a careful implementation of the core algorithms was felt.
The implementation involved careful study of various research papers written by Clenshaw, Olver, Turner and Lozier
2-3
Functions Implemented
Functions Implemented
◆ ToLIO[n_Real] :
◆ ToLIO[n_Real] :
The ToLIO[n_Real] function takes any Real Number as input and converts it into an LIO[sign, level, index] object, as per the original Ordinary Level-Index Arithmetic notation of a number, having a sign, a level and an index.
Note: Sign is always either +1 or -1.
Note: Sign is always either +1 or -1.
In[]:=
ToLIO[1234567]
Out[]=
LIO[1,3,0.971131]
◆ PowerForm[ LIO[sign, level, index] ] :
◆ PowerForm[ LIO[sign, level, index] ] :
The PowerForm[LIO[sign,level,index]] function takes any LIO[sign, level, index] object as input and converts it into a nice, readable level-index format in base 10, so that it looks like a Power Tower of 10s with an index at the end.
In[]:=
PowerForm[LIO[1,14,0.677]]
Out[]=
0.438599
10
10
10
10
10
10
10
10
10
10
10
10
10
◆ FromLIO[ LIO[sign, level, index] ] :
◆ FromLIO[ LIO[sign, level, index] ] :
The FromLIO[LIO[sign,level,index]] function takes any LIO[sign, level, index] object as input and converts it into a floating-point number if it does not overflow. If it overflows in normal floating-point notation, the PowerForm[] is invoked automatically, and a level-index format of the number in base 10 is returned.
In[]:=
FromLIO[LIO[1,3,0.9]]
Out[]=
120592.
In[]:=
FromLIO[LIO[1,7,0.65]]
Out[]=
0.412713
10
10
10
10
10
10
◆ LevelIndexArithmetic[expr_] :
◆ LevelIndexArithmetic[expr_] :
The LevelIndexArithmetic[expr_] function takes any arithmetic expression as input, converts it to LIO[ sign, level, index] object, performs desired arithmetic operations on them, and then finally returns the result as an LIO[ sign, level, index] object.
In[]:=
LevelIndexArithmetic++
86
299
88
1
2
10
864
677
99
8
233
29
7
Out[]=
LIO[1,6,0.768246]
Note: It’s generally a good idea to wrap the LevelIndexArithmetic[] function with FromLIO[], to get the final output in a nice, readable format.
In[]:=
LevelIndexArithmetic++//FromLIO
86
299
88
1
2
10
864
677
99
8
233
29
7
Out[]=
0.53
10
10
10
10
10
Handling Divisions
Handling Divisions
Since Division operations of two numbers inside LevelIndexArithmetic[] function would actually get interpreted as Multiplication of two LIO[]s with the second one having a negative index, as since negative index of LIO[] is not defined as per the normal level-index notation system, hence it would throw an error if Division operation is tried inside one single LevelIndexArithmetic[] function.
The same can be handled in the following manner:
Ifyouwanttodo,simplyconvertthenumeratorandthedenominatoreachtoLIO[]sfirstusingLevelIndexArithmetic[]function,andthendotheDivision.
309
677
88
10
97
88
10
In[]:=
LevelIndexArithmeticLevelIndexArithmetic//FromLIO
309
677
88
10
97
88
10
Out[]=
0.46864
10
10
10
10
10
A Look into the Backend
A Look into the Backend
The Addition and Subtraction operations were implemented by forming three Recursive Functions, as suggested by the original algorithm in the paper “Level-Index Arithmetic Operations” by Clenshaw and Oliver.
4
The Multiplication, Division and Exponentiation operations were implemented using the following rules :
x*y=
Log[x]+Log[y]
x/y=
Log[x]-Log[y]
y
x
Log[x]*y
The Full Code can be seen here :
The Full Code can be seen here :
Show full code
Show full code
A Few More Interesting Operations and Test-Cases
A Few More Interesting Operations and Test-Cases
Consistent results for Non - Integral Power Towers
Consistent results for Non - Integral Power Towers
In[]:=
LevelIndexArithmetic//PowerForm
Pi
E
E
E
E
E
Out[]=
0.986219
10
10
10
10
10
10
In[]:=
LevelIndexArithmetic//FromLIO
223.869
8.9913
3.8764
2.999999
10
Out[]=
0.367168
10
10
10
10
10
10
Comparator Functions
Comparator Functions
We can now successfully compare huge Power Towers in Mathematica without the problem of overflow, which might not be possible till date using normal computers or most other calculators so easily.
We can now successfully compare huge Power Towers in Mathematica without the problem of overflow, which might not be possible till date using normal computers or most other calculators so easily.
In[]:=
LevelIndexArithmetic<
888
88
8
1024
48
128
Out[]=
False
Summary
Summary
A few functions were successfully fabricated using the Wolfram Language to carry out arithmetic operations of huge numbers in Mathematica using Level-Index Arithmetic, which would otherwise overflow in normal floating-point notation.
Further Works
Further Works
◼
Forming more test cases and checking the current implementation rigorously for any edge-case.
◼
Including this in the Wolfram Function Repository.
◼
Extending the implementation to Symmetric Level-Index Arithmetic (SLI).
◼
Devicing an algorithm to convert huge factorials to Level-Index Objects.
◼
Extending the functions to Complex realms.
Keywords
Keywords
◼
overflow
◼
level-index
◼
numerical analysis
◼
computer arithmetic
◼
precision
◼
exponentiation
◼
Power Towers
◼
Tetration
Acknowledgment
Acknowledgment
Mentor: Carl Woll
I would like to thank my mentor for guiding me towards a successful implementation, the friendly and helpful teaching assistants (especially Daniel Sanchez,Jesse Friedman and Philip Maymin ) for their 24x7 assist even at all kinds of silly problems I ran into, Stephen Wolfram for his suggestions to take up this project and finally also my friend Nikolay Murzin for his support during the course of the project. They were always eager to help me out whenever I got stuck at any stage.
I would also like to thank my mother for staying up late with me when I worked on hours without sleep on the project on the last few days, and my father for constantly supporting me.
I would also like to thank my mother for staying up late with me when I worked on hours without sleep on the project on the last few days, and my father for constantly supporting me.
References
References
◼
by Robert Munafo
◼
( C. W. Clenshaw and F. W. J. Oliver SIAM Journal on Numerical Analysis Vol. 24, No. 2 (Apr., 1987), pp. 470-485 )
◼
(Wikipedia)
In[]:=
1 https://dl.acm.org/doi/10.1145/62.322429
2 https://academic.oup.com/imajna/article-abstract/8/4/517/758814?redirectedFrom=fulltext
3 https://www.jstor.org/stable/2157569?seq=1
4 https://dl.acm.org/doi/10.1145/62.322429
Cite this as: Swastik Banerjee, "Implementation of Level-Index Arithmetic for Very Large Numbers" from the Notebook Archive (2020), https://notebookarchive.org/2020-07-6i9f1t4
Download
