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 2024-11-10.)
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.)
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.
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.
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.
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.
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 |
|---|---|
| 10 | 3.0 |
| 20 | 6.2 |
| 100 | 53 |
| 200 | 82 |
| 1,000 | 136 |
| 2,000 | 253 |
| 10,000 | 435 |
| 20,000 | 585 |
| 100,000 | 1311 |
| 200,000 | 1833 |
| 1,000,000 | 4231 |
| 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.
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 |
|---|---|
| 10 | 4.5 |
| 20 | 7.1 |
| 100 | 68 |
| 200 | 132 |
| 1,000 | 262 |
| 2,000 | 376 |
| 10,000 | 678 |
| 20,000 | 935 |
| 100,000 | 2010 |
| 200,000 | 2776 |
| 1,000,000 | 6288 |
| 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.
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.
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:
/e modifier, which treat the right-hand-side of the
substitution as a Frink expression. The variable names are available in
the Frink code. Named capture groups are specified
as (?<varname>pattern). For example, the
following increments each integer in a string:
Original Frink, which used
Perl-style $1, $2... to refer to captured
matches:
"There are 3 lights. My ship is the NCC-1701-D." =~ %s/(\d+)/eval[$1]+1/eg
Frink: The Next Generation, which allows named capture groups to be used as variable names:
"There are 3 lights. My ship is the NCC-1701-D." =~ %s/(?<num>\d+)/eval[num]+1/eg
There are 4 lights. My ship is the NCC-1702-D.
\u{h...h} (Frink notation)
and \x{h...h} (Java regex notation)
where h...h represents from 1 to 6 hexadecimal
digits that represent the desired Unicode codepoint.
\xhh
where hh represents exactly 2 hexadecimal digits
that represent the Unicode character.
\0
\a (use \u0007 instead)
\e (use \u001B
instead)
\cX
(specify it with its Unicode character instead.)
These problematic patterns are still allowed on the left-hand side of a substitution expression, but that may change.
[[:alpha:]] and [[:digit:]] are no longer
available and have been replaced with Unicode regular expression classes
as specified
in Unicode
Technical Standard 18: Unicode Regular Expressions. Again, see
Java's documentation for its Pattern
class to see other supported Unicode patterns.
| Old (POSIX) | New (Unicode) |
|---|---|
| [[:lower:]] | \p{Lower} |
| [[:upper:]] | \p{Upper} |
| [[:ascii:]] | \p{ASCII} |
| [[:alpha:]] | \p{Alpha} |
| [[:digit:]] | \p{Digit} |
| [[:alnum:]] | \p{Alnum} |
| [[:punct:]] | \p{Punct} |
| [[:graph:]] | \p{Graph} |
| [[:print:]] | \p{Print} |
| [[:blank:]] | \p{Blank} |
| [[:cntrl:]] | \p{Cntrl} |
| [[:xdigit:]] | \p{XDigit} |
| [[:space:]] | \p{Space} |
/uU regex options essentially unnecessary and
obsolete.
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:
yychar type has been changed from int
to long so Frink program files or files parsed by a JFlex
lexer (the other JFlex lexer in Frink is for JSON files) can be larger
than 2 GB.
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.)
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:
floor, ceil,
round, and truncate functions. These were
significant in some programs.
Please send comments or questions to Alan Eliasen.