Message Boards

GROUPS:

Computer Science Mathematics Computational Systems Wolfram Language Numerical Computation Computer-Based Maths Wolfram Summer School

Swastik Banerjee

[WSS20] Implementation of Level-Index Arithmetic for Very Large Numbers

Swastik Banerjee, SRM Institute of Science and Technology

Posted 1 year ago

3665 Views

6 Replies

21 Total Likes

Follow this post

Abstract 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 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 General :Overflow occurred in computation. General :Overflow occurred in computation. 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 Level-index Arithmetic introduced by Clenshaw and Olver 1 in 1984. The idea of the level - index system is to represent a non - negative real number 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. 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. 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 23 64 89 233 69 50000 888 88 8 + 222222 22222 2222 222 22 2 //FromLIO Out[]= 0.209919 10 10 10 10 10 10 10 10 Research and Implementation The implementation involved careful study of various research papers written by Clenshaw, Olver, Turner and Lozier 2-3 ,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 to make the results more accurate. Functions Implemented ◆ 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. In[]:= ToLIO[1234567] Out[]= LIO[1,3,0.971131] ◆ 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] ] : 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_] : 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 86 299 88 1 2 10 + 864 677 99 8 + 233 29 7 //FromLIO Out[]= 0.53 10 10 10 10 10 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 309 677 88 10 97 88 10 ,simplyconvertthenumeratorandthedenominatoreachtoLIO[]sfirstusingLevelIndexArithmetic[]function,andthendotheDivision. In[]:= LevelIndexArithmetic 309 677 88 10 LevelIndexArithmetic 97 88 10 //FromLIO Out[]= 0.46864 10 10 10 10 10 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 1 The Multiplication, Division and Exponentiation operations were implemented using the following rules : xy= Log[x]+Log[y]  x/y= Log[x]-Log[y]  y x = Log[x]*y  The Full Code can be seen here : Show full code  A Few More Interesting Operations and Test-Cases Consistent results for Non - Integral Power Towers In[]:= LevelIndexArithmetic Pi E E E E E  //PowerForm Out[]= 0.986219 10 10 10 10 10 10 In[]:= LevelIndexArithmetic 223.869 8.9913 3.8764 2.999999 10 //FromLIO Out[]= 0.367168 10 10 10 10 10 10 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. In[]:= LevelIndexArithmetic 888 88 8 < 1024 48 128  Out[]= False 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 ◼ 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 ◼ overflow ◼ level-index ◼ numerical analysis ◼ computer arithmetic ◼ precision ◼ exponentiation ◼ Power Towers ◼ Tetration 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. References ◼ Hypercalc by Robert Munafo ◼ Level Index Arithmetic Operations ( C. W. Clenshaw and F. W. J. Oliver SIAM Journal on Numerical Analysis Vol. 24, No. 2 (Apr., 1987), pp. 470-485 ) ◼ Tetration (Wikipedia) ◼ Wolfram Language Documentation 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 1 https://dl.acm.org/doi/10.1145/62.322429