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:

**BigDecimal Replacement:**Replace the old, highly-modified IBM BigDecimal library with Java's built-in BigDecimal library for floating-point math.**Regular Expression Replacement:**Replace the old OROMatcher regular expression library with Java's internal regular expression library, which does Unicode better, and has many more features.**JFlex Replacement:**Update Frink's lexer to JFlex 1.6.1 which allows better Unicode support in Frink programs.**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.

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-30.)

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.)

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(n^{2}) to approximately
O(n^{1.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(n^{1.465}), and Karatsuba multiplication has an
asymptotic efficiency of O(n^{1.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 ```
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 * 10^{101008905}, 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(`

which means
that a number cannot be shifted left by more than
*int*)`2`

bits, which sets some of these limits. Java
1.8, instead of introducing better API functions, introduced some hard
limits that enforce these limitations.
^{31}-1

Division has been sped up for all argument sizes. In addition, the
asymptotic behavior has improved from O(n^{2}) to approximately
O(n^{1.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, 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:

- Named capture groups are allowed in substitutions which use the
`/e`

modifier, which treat the right-hand-side of the substitution as a Frink expression. The variable names are available in the Frink code. - Vastly improved Unicode support and POSIX code class support.
- Improved character classes, including union, intersection, and subtraction.
- All features of Java's Pattern class are supported.
- All regular-expression-using expressions have been updated.
- This reduces code size and improves startup time.

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:

- Improved performance of the
`floor`

,`ceil`

,`round`

, and`truncate`

functions. These were significant in some programs. - Improved performance of writing graphics to HTML, SVG, and SVGZ formats. Some programs are now up to 13 times faster when writing these files.

Please send comments or questions to Alan Eliasen.