Documentation * What's New * FAQ * Download * Frink Applet * Web Interface * Sample Programs * Frink Server Pages * Frink on Android * Donate
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.
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.
You can download the current version of Frink: The Next Generation here:
(current build is compatible with Java 1.6 or later, and released 2018-09-24.)
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:
frink-tng.jar in those
examples, of course.)
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.
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.
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 Digits||Speedup factor|
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 asymptotic 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 asymptotic 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
speedup[n] := 4.2293 n^0.497
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
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.
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 Digits||Speedup factor|
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.
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, eBinarySplitting.frink, and ArbitraryPrecision.frink, and the integer-based square root routines karatsuba.frink 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.
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.
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:
/emodifier, which treat the right-hand-side of the substitution as a Frink expression. The variable names are available in the Frink code.
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 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 various performance improvements include:
truncatefunctions. These were significant in some programs.
Please send comments or questions to Alan Eliasen.