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
**2024-05-09**.)

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(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 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 * 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), 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:

- 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. Named capture groups are specified as`(?<`

. For example, the following increments each integer in a string:*varname*>*pattern*)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.`

- Vastly improved Unicode support and Unicode character class support.
- Improved character classes, including union, intersection, and subtraction.
- All features of
Java's Pattern class are supported, with a few exceptions:
- The left- and right-hand side of a substitution expression can now
accept high Unicode characters in both Frink and Java format, that is in
the format
`\u{`

(Frink notation) and*h...h*}`\x{`

(Java regex notation) where*h...h*}

represents from 1 to 6 hexadecimal digits that represent the desired Unicode codepoint.*h...h* - The right-hand side of a substitution expression can now
contain character escapes in the format
`\x`

where*hh*

represents exactly 2 hexadecimal digits that represent the Unicode character.*hh* - The right-hand side of a substitution expression currently expressly
can
*not*contain some of the antiquated and problematic character escapes defined in Java's Pattern class. The*un*supported patterns are:- Octal escapes beginning with
`\0`

- The alert (bell) character
`\a`

(use`\u0007`

instead) - The escape character
`\e`

(use`\u001B`

instead) - The escape sequence for control characters
`\c`

(specify it with its Unicode character instead.)*X*

These problematic patterns are still allowed on the left-hand side of a substitution expression, but that may change.

- Octal escapes beginning with

- The left- and right-hand side of a substitution expression can now
accept high Unicode characters in both Frink and Java format, that is in
the format
- The old-style (POSIX-style) character classes that look
like
`[[: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} - As of the 2020-07-13 release, all of the Unicode character classes
above use full Unicode properties by default. This fixes the broken
behavior of the Java 1.6 release when running on Java 1.7 and later and
makes the
`/uU`

regex options essentially unnecessary and obsolete. - 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 2020-02-29:** JFlex 1.8.0 was recently
released. It has some desirable improvements, such as:

- Much smaller Unicode parsers (memory decreased from ~4 MB to ~20kB)
- The
`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. - Unicode 10.0, 11.0, 12.0, and 12.1 are supported.
- Unicode Emoji properties are supported for Unicode versions 8.0+.

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:

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