Experimental Frink Features

Documentation * What's New * FAQ * Download * Frink Applet * Web Interface * Sample Programs * Frink Server Pages * Frink on Android * Donate

Introduction

Greetings, Starfighter! You have found the secret page that describes experimental and undocumented features of the Frink programming language!

Many of these features have secretly existed in your copy of Frink for years, but haven't been officially documented because they may change (hopefully for the better.) Frink tries very hard not to invalidate old programs, which is why experimental features are not openly documented.

This page also contains discussion of upcoming features such as Frink: The Next Generation which will break compatibility with (admittedly ancient) versions of Java in order to add improved features.

Table of Contents

Frink: The Next Generation

The intent of the Frink: The Next Generation project is to:

Frink has always tried to be compatible with very old versions of Java and Android. In fact, Frink runs on Java 1.1, and better (Swing) graphics run on Java 1.2 due to conscientious use of always-available functions, and careful loading-by-name. The weakness is that modern data structures could not be used.

At the moment, Frink: The Next Generation runs on Java 1.6, but this may be updated to Java 1.7 or later as new features are added. Java 1.8 is necessary to get the benefits of faster floating-point and integer.

More information about these features is below.

Downloading Frink: The Next Generation

You can download the current version of Frink: The Next Generation here:

Download frink-tng.jar

(current build is compatible with Java 1.6 or later, and released 2023-12-31.)

You can replace your current frink.jar file with this file in your startup scripts, or simply double-click it on most operating systems to launch Frink in GUI mode! See the Running Frink section of the documentation for ways to run it. (Note: replace frink.jar with frink-tng.jar in those examples, of course.)

Frink Server Pages

There is an experimental WAR file for running Frink: The Next Generation on your webserver to run Frink Server Pages. See that documentation for more details on modifying it.

Download frink-tng.war

The current version of this file is built with Java 1.6 and the Servlet 3.1 API, which means it should be backward-compatible with many servlet containers.

BigDecimal Replacement

This task was to replace the old, highly-modified IBM BigDecimal library with Java's built-in BigDecimal library for floating-point math. When run under Java 1.8 or later, this gives significant performance improvements when calculating with floating-point numbers with many digits. The old BigDecimal library became extremely slow at the thousands or ten thousands of digits.

Frink Improvements

Did you know that Java and all of its derived languages became many orders of magnitude faster at mutliplying and dividing arbitrary-precision integers and floating-point numbers because of Frink? That's because Frink contributed much, much better algorithms to Java. Many algorithms became millions of times faster (such as exponentiation by powers of two) and others became tens of thousands of times faster (for example, multiplication and base conversion.) Operations that would take days before can be done in seconds due to Frink's contributions.

It took 10 or 11 years of work from Frink to get the Java developers to check in the vastly improved algorithms, including Karatsuba multiplication, Karatsuba squaring, 3-way Toom-Cook multiplication and squaring, divide-and-conquer Schoenhage-Strassen base conversions, and more. My colleague Tim Buktu also contributed algorithms for Burnickel-Ziegler division (and has pending algorithms for Barrett division and FFT multiplication that the Java developers have not checked in.) They were finally incorporated into Java 1.8. The performance numbers below require that you use Java 1.8 or later to run Frink: The Next Generation.

Status: A full replacement is complete in the branch, and is undergoing testing. The outstanding issue is that many Android implementations have broken number formatters.

Multiply Speedup

Multiplication has been sped up for all argument sizes. In addition, the asymptotic behavior has improved from O(n2) to approximately O(n1.5) or better. When multiplying two 10-million-digit numbers, time is reduced from over 9 days down to 62 seconds!

Decimal DigitsSpeedup factor
103.0
206.2
10053
20082
1,000136
2,000253
10,000435
20,000585
100,0001311
200,0001833
1,000,0004231
10,000,000(est) 13000
101,000,000(est) 40000

One impact of these improvements is that the time to multiply two 101-million-digit numbers has been reduced from approximately 2.7 years down to 36 minutes!

(101 million digits is approximately the limit for digits in a floating-point number or integer. The technical reasons are discussed below.)

Technical Note: 3-way Toom-Cook multiplication has an asymptotic efficiency of O(n1.465), and Karatsuba multiplication has an asymptotic efficiency of O(n1.585), where n is the number of digits in the number. My improvements to Java 1.8 contain both Karatsuba and 3-way Toom-Cook multiplication.

On a 4 GHz AMD processor, the empirically-found time for the old multiplication routines, for a number with n digits, can be written as approximately:

tOld[n] := 7.2778e-9 s n^2.009

while the empirically-found time for the new multiplication routines is approximately:

tNew[n] := 1.7208e-9 s n^1.512

the asymptotic speedup factor can be calculated as c1/c2 n^(x1-x2):

speedup[n] := 4.2293 n^0.497

Java's BigInteger class is limited in some cases to approximately 1.56 * 10101008905, or 101,008,905 decimal digits. In some cases, it can be made to generate up to about 646,456,000 decimal digits. As a result, the maximum number of digits that can be represented in a BigDecimal may be limited to about 101,008,905 decimal digits. This is because of a limitation in the API functions like BigInteger.shiftLeft(int) which means that a number cannot be shifted left by more than 231-1 bits, which sets some of these limits. Java 1.8, instead of introducing better API functions, introduced some hard limits that enforce these limitations.

Divide Speedup

Division has been sped up for all argument sizes. In addition, the asymptotic behavior has improved from O(n2) to approximately O(n1.5) or better. When dividing two 10-million-digit numbers, time is reduced from over 11 days down to 49 seconds!

Decimal DigitsSpeedup factor
104.5
207.1
10068
200132
1,000262
2,000376
10,000678
20,000935
100,0002010
200,0002776
1,000,0006288
10,000,000(est) 19000

When calculating things like millions of digits of e, the improvements are most pronounced. The new version of Frink can calculate 1 million digits of e in 17 seconds, while the old version took 9435 seconds. This is a factor of 544 improvement. The ratio gets even better when calculating 100 million digits of e, which was unfeasible with the old Frink (it would take literally years,) but takes 6041 seconds with the new Frink.

It's ironic that Frink was not using Java's BigDecimal, as the significant improvements made to Java's BigInteger class that arrived in Java 1.8 came from Frink. (BigDecimal uses BigInteger to do most of its operations internally.) I contributed much faster algorithms for Karatsuba multiplication, Karatsuba squaring, Toom-Cook multiplication and squaring, Schönhage-Strassen base conversion, improvements to exponentiation, and more, and worked with a colleague (Tim Buktu) to contribute Burnikel-Ziegler division, all of which became part of Java 1.8. (Android usually uses native implementations from OpenSSL or BoringSSL for BigInteger calculations.) Tim also contributed an FFT-based multiply and Barrett division, but these are rather complex and have not been reviewed and included so far. It took me 11 years of work to get them to review and include the changes they did. Thanks to Brian Burkhalter for reviewing and integrating the changes.

Arbitrary-Precision Functions

Many of the sample programs that calculate arbitrary-precision transcendental functions and constants, such as pi.frink, piChudnovsky.frink (which has been optimized for the new Frink in piChudnovskyNew.frink), e.frink, eBinarySplitting.frink, and ArbitraryPrecision.frink, and the integer-based square root routines karatsuba.frink (which are now better replaced by sqrtWayne.frink in Frink:TNG) used mostly integer operations because floating-point operations were so much slower for large numbers of digits. Now, with floating-point operations that are orders of magnitude faster, these can be rewritten and better integrated, and arbitrary-precision floating-point operations can be much faster.

BigDecimal Issues

When testing on Android, it immediately became apparent that the java.math.DecimalFormat class implementation used on many Android implementations is completely broken and cannot print more than a fixed number of digits (309 or 340 digits in some cases). This was traced to the use of the ICU4J library, which contains an implementation that simply doesn't understand the point of BigDecimal or BigInteger, that is, to calculate with an essentially unlimited number of digits.

This was filed as bug #13616 (link opens in new window) which was, after some weird excuses, closed as "working as designed." This makes no sense at all. It's not clear how to fix platforms with this broken implementation.

Regular Expression Replacement

The intent is to replace the old OROMatcher regular expression library with Java's internal regular expression library, which does Unicode better, and has many more features.

Java did not include a regular expression library until Java 1.4, and many of its current features, including named groups and Unicode Character Classes did not exist until Java 1.7.

Status: A full replacement is complete in the branch, and is undergoing testing. All tested code is working properly. The features include:

JFlex Replacement

Replaces the JFlex lexer library with JFlex 1.6.1, which gives improved Unicode support in the parser, including updated emoji support, better support for subscripts, and enhanced Unicode and POSIX character classes.

Status: A full replacement is complete, and is available in the current public release. All tested code is working properly.

Update 2020-02-29: JFlex 1.8.0 was recently released. It has some desirable improvements, such as:

The largely undesirable change is that this will force Frink:TNG to require Java 1.7 to run (and Java 1.8 to build.) Currently, Frink:TNG is compatible with Java 1.6. It's not clear if Frink:TNG will be upgraded to this version. If we can hack the build to support Java 1.6, as was done for JavaCUP, the update might happen sooner rather than later. Or, yet another build might be produced (that probably targets Java 1.8.)

JavaCUP Replacement

Update Frink's parser to JavaCUP version 11.b. This will pave the way for better error messages, syntax trees, and autocompletion in the future. There have been bugfixes made in this library since the previous version, but none of the bugs have apparently affected Frink.

JavaCUP was slightly modified and recompiled to be compatible with Java 1.6 and later. (The shipped configuration compiles to Java 1.8.)

Status: A full replacement is complete, and is available in the current public release. All tested code is working properly. Parsing speed remains basically unchanged.

Other Performance Improvements

Other various performance improvements include:


Please send comments or questions to Alan Eliasen.