Letter to the Editor of The ModulaTor Erlangen's First Independent Modula-2 Journal concerning VPCalc VARIABLE PRECISION CALCULATOR Integer + Floating + Scientific The article on the "Ackermann Function", by G~unter Dotzel appeared in "The ModulaTor 03/91" (see below for a directory listing). It was also published under the title "A Function to end all functions" in "Algorithm 10/91". ===================== Dear Editor, I thoroughly enjoyed your article. But you too can compute A(4,2), on your PC. I am sending you a copy of my program VPCalc. Load the program and type SetMax(20,000) 20,000 M Ax4y2 = 2^(2^(2^(2^2))) - 3 WriteN("Ax4y2") and A(4,2) will be computed and written to the file Ax4y2.VPN. The commands are not case sensitive and the commas (,) are not needed in numbers. The "Ax4y2 =" is better since it is stored inside the output file. It takes about 29 seconds for VPCalc to compute A(4,2) on a 33 MHz 486DX machine. I have stored the value of A(4,2) that I computed and a program, Ackerman.Pas, I wrote to compute A(x,y) in files on the disk enclosed. If you inspect the output file Ax4y2.VPN, it looks like: Ax4y2 = m.n E+19728, m.n =2.00352 99304 06846 46497 90723 51560 255 ...E+19728 From this you can see that A(4,2) has 19,729 decimal digits, not 19,728 as you stated in your article, a minor flaw. Using function procedure written in Pascal: ------------------------------------------- function A(x, y : LongInt) : LongInt; { The Ackermann function is the simplest example of a well-defined total function which is computable but not primitive recursive. See the article "A function to end all functions" by Gunter Do”tzel, Algorithm 2.4, Oct 1991, Pg 16. The function f(x) = A(x, x) grows much faster than polynomials or exponentials. The definition is: 1. If x = 0 then A(x, y) = y + 1 2. If y = 0 then A(x, y) = A(x-1, 1) 3. Otherwise, A(x, y) = A(x-1, A(x, y-1)) } begin if (x = 0) then A:= y+1 else if (y = 0) then A:= A(x-1, 1) else A:= A(x-1, A(x, y-1)); end; { A } ------------ it was easy to determine that: A(0,y) = y+1 A(1,y) = y+2 A(2,y) = 2y +3 A(3,y) = 2^(y+3) -3 The formula for A(3,y) published in your article was "2 raised to the power of 2y+3", a typographical error. From your article I deduced: A(4,y) = 2^(2^(2^...2)) -3, where there are y+2 2's My program Ackerman.PAS also computes the total number of times that the A(x,y) function is called for an initial x,y. It would appear that the number of times called, AC(x,y), grows even faster than the Ackermann function itself. For example: A(3,6) = 509 and AC(3,6) = 172,233 A(3,7) = 1021 and AC(3,7) = 693,964 A(3,8) = 2045 and AC(3,8) = 2,785,999 ----------------------------------------- My program VPCalc is quite unique in its ability to perform scientific calculations at whatever precision desired, up to a ridiculously large precision. To use the program, first browse the file VPCalc.Doc. Some of VPCalc's features are: - It is a variable precision scientific calculator. - Written in object-oriented Pascal - It is its own full program language interpreter. - Integrated code parsing, interpreting and evaluating. - Floating point numbers normalized from both ends. Neither most significant nor least significant zeros stored in memory. - Dynamic memory allocation as new variables are introduced or changed. - Pop up help menus. - Full command line editing features. - Internal calculations performed at higher precision to minimize round-off error. - Each Taylor series terms only computed to precision required. - Optimal reduction of argument for Taylor series. Read the section on "Transcendental Function Evaluation" near end of VPCalc.Doc file for other original methods. The new version attempts to perform all calculations as if they were done to infinite precision and then rounded to even. The IEEE floating point standard requires that add, subtract, multiply, divide, and square root be done this way. It is not a requirement for the transcendental functions, but I put guard digits on them also. The calculations done by VPCalc are a lot more stable now. Also the new version has many new features to make the program easier to use. For example, it saves the history of operator entries for re-execution like XTree Pro Gold. Also, the complete state of the calculator can be saved to disk and restored at a later time. Some of VPCalc's new features are: - Save/Restore history of previous operator entries. - Save/Restore current calculator configuration. - Save/Restore the complete state of the calculator. - Clear history of previous operator entries. - Restore Last Top, like Last x on HP calculators. - Enable/Disable save Last Top. - Fix display vice scientific notation for low precision numbers. - Enable/Disable force scientific notation. Run a code file procedure. - Read a number file procedure. - Write a number file procedure. - Run VPCalc code file AUTOEXEC.VPC on startŠup. - A:> VPCALC xxxxxxxx.VPC will run file xxxxxxxx.VPC Sincerely, Harry J. Smith, 19628 Via Monte Drive, Saratoga, CA 95070, U.S.A. ========================== Dear Harry, It still holds true, that a computer can't compute Ackermann(4,2) using it's definition (i.e. the recursive algorithm). As you did, one has to analyse the function and construct an alternative algorithm. Did you try Ackermann (4,3)? Best wishes, G~unter Dotzel Editor of The ModulaTor ======================= Dear Editor, I agree that the Ackermann function is "A function to end all functions." You asked if I tried A(4,3). Well yes, but my program VPCalc only handles a value up to about 10^15,032,385,525 and can only handle 114,639 decimal digits in the mantissa. A(4,2) fits my niche well, but A(4,3) is way out there. It would take more than A(4,2) seconds to compute A(4,3) and the computer would need more than A(4,2) bits of memory. This cannot be done in this universe. Remember A(4,2) = 2.00352...E+19728. Please feel free to distribute the copy of VPCalc that I sent you, it is ShareWare. Sincerely, Harry J. Smith, 19628 Via Monte Drive, Saratoga, CA 95070, U.S.A. ========================== VARIABLE PRECISION CALCULATOR Integer + Floating + Scientific Transcendental functions computed to thousands of decimal places. Dynamic range of 10 to 15032385525. Send $5.00 for IBM-PC diskette: Harry J. Smith 19628 Via Monte Dr. Saratoga, CA 95070 If you have a copy of this diskette and 1) it has been damaged 2) you have sent me $5.00 for it 3) you have not asked me to send a new copy then ask me to send you a new one. If you have a copy of this diskette and 1) you plan to keep it 2) you have not sent me $5.00 for it then send me $5.00 to be a registered owner. Anyone may freely copy and distribute this diskette as long as they include this READ-ME file. Harry Smith =========== Editor's note: I've uploaded VPCalc.LZH into this forum. Try VPCALC and enjoy it. It's faster than lightening. ======================= The ModulaTor Erlangen's First Independent Modula-2 Journal DIRECTORY Directory of articles already appeared and to appear in The ModulaTor from Jul-1990 to Dec-1991 ([volume, issue] author, title [sub-title] (number_of_pages) [ remarks]): [0, 0] Gunter Dotzel, 0.0. Random Modula-2 News. 0.1 Report from the 1st International Modula-2 Conference in Bled/Yugoslavia, Oct-1990. 0.3. Information on the 1st European Modula-2 Conference to be held at the Polytechnic of Wales, Dec-1990. Editorial: Call for Articles for Publication in The ModulaTor (4) [0, 1] Gunter Dotzel, Does Modula-2 Generate Racehorses? Comparison of Compiler Generated Code Quality for Floating Point Arithmetic (4) Also appeared under the same title in ACM SIGPLAN Notices, Dez-1990. [0, 2] Gunter Dotzel, The ISO/IEC JTC1/SC22 D106/N336 Modula-2 Language Changes according to the Third Working Draft Standard (8) [0, 3] Gunter Dotzel, Modula-2 Beats C even in System Programming. A Comparison of the Programming Languages Modula-2 and C on VAX/VMS. An earlier version of this article, entitled Her mit dem alten Datum (How to modify the revision date of a file), was also published in a DECKBLATT, Markt & Technik Verlag, Haar bei Munchen/F.R.G., 1991 (4) [0, 4] Anja Schumacher, XWindows and UIL Programming Using Modula-2. Two Examples show how to use DEC's XWindows interface (this includes ICOMOD.MOD, which displays a wire-frame rotating icosahedron, with hidden lines removed. ICOMOD bounces a bounding box inside the window. This file was uploaded to CompuServe's CodePort Forum and can be downloaded from the Modula-2 library.) A third examples shows how to write a program for the DECWindows Toolkit. All programs run on a VAX`station under VMS V5.4 (8) [1, 0] Gunter Dotzel, The Oberon-Style I/O-Library for Modula-2. A Description of the Oberon I/O-modules from Wirth's Oberon System (4) [1, 1] Gunter Dotzel, Modula-2 and the COMPLEX type. An Evaluation of the Compiler's Complex Extension (4) [1, 2] Gunter Dotzel, The Ackermann Function. A guided trip into the theory of computability (4) Also appeared in revised form under the title A function to end all functions in Algorithm, Recreational Programming, edited by A.K. Dewdney (Oct-91). Contact: L.D. Magguilli, Algorithm, PO Box 29237, Westmount Postal Outlet, 785 Wonderland Road S., London, Ontario N6K 1M6, Canada [1, 2.1] Gunter Dotzel, Components of the Modula-2 Compiler Kit. A Quantitative Description of all Components of MVR V3 (4) [1, 3] Gunter Dotzel, The Medium is the Embassy. Personal Thoughts on Messages, Computer Languages and Risky Business (2) [1, 4] John Bullock, Audio, Software and Hardware Perspectives. News and speculations about the future from the other side of the ocean (4) [1, 5] Gunter Dotzel, The EDISON Multiprocessor Language. A modular multiprocessor programming language designed by Per Brinch Hansen and it's portation to VMS (3) [1, 6] Gunter Dotzel, Comparison of the Edison & Modula-2 Language Features. (3) [1, 7] Gunter Dotzel, How to improve acceptance of ISO-Modula_2? (5) [1, 7.1] Gunter Dotzel, Report from the Sixth ISO SC22/WG13 Modula_2 Working Group Meeting (2) [1, 8] Elmar Baumgart, The ISO Modula-2 I/O-Library A Collection of Definition Modules (9) [1, 9] Gunter Dotzel, CAF: The ShareWare PC-Version of ModulaWare's Modula-2 Library & Tools (5) [1, 10] Helmut Wiacker, Batch Queue Infortmation under VMS (5) [1, 10.1] Gunter Dotzel (Editor), Last minute pointer to Modules & Definitions, a Modula-2 ShareWare Magazine (1) [1, 11] Gunter Dotzel, CRY: Cryptification Tool written in Oberon (5). Includes the above conversation (letter to the editor) on VPCalc. Impressum: The ModulaTor is published monthly. Annual subscription rate: no charge for ModulaWare's VAX/VMS Modula-2 Compiler licensees with annual software support; all others DM 60.- for Europe and US$ 40.- elsewhere, including postage and handling charges. Airmail delivery on request. The ModulaTor is an unrefereed journal. Technical papers are to be taken as working papers and personal rather than organizational statements. Items are printed at the discretion of the Editor based upon his judgement on the interest and relevancy to the readership. Letters, announcements, and other items of professional interest are selected on the same basis. Guidelines for submission of manuscript and correspondence concerning advertisements should be send to the office of publication: The ModulaTor, c/o ModulaWare GmbH, Wilhelmstr. 17A, W-8520 Erlangen/F.R.Germany. The Editor of The ModulaTor is G~unter Dotzel; he can be reached at the same address or by phone: +49 (9131) 208 395, by fax: +49 (9131) 28205 or by email, either g_dotzel@ame.nbg.sub.org or 100023.2527@compuserve.com ============== GD 30-Dec-1991