New classes for arbitrary precision arithmetic in ABAP

1. Introduction

Typically there are two kinds of improvements to a programming language. This first kind makes difficult things easy and the second kind makes impossible things possible. This blog post is about arbitrary precision arithmetic which falls into the second class: making previously impossible things possible in ABAP.

You can already calculate with really large numbers in ABAP when using the INT8 or DECFLOAT34 datatype. But you can not calculate with arbitrary precision yet. With both datatypes, you also have the risk of overflow.

Although DECFLOAT34 can operate on really large numbers, the precision is only 34 digits. This means you get arbitrary wrong results when doing more complex calculations. A typical problem arises when you add and subtract numbers of different size categories, for example:

larger_number + smaller_number - larger_number = 0

The reason is that the large number does not have enough precision to reflect the addition of the small number. If you subtract the large number again, you will get zero. Small does not mean that the number is really small, only that it is much smaller than the larger number. So 10000 may be small in this context.

Many programming languages offer the possibility of arbitrary precision arithmetic. Java for example has the BigInteger and BigDecimal classes, Pythons integer datatype is arbitrary precision by default, and C# also offers a BigInteger datatype. The C++ language has the well-known GMP and MPFR libraries for arbitrary precision arithmetic.

2. Different kinds of arbitrary precision arithmetic

Typically there are three kinds of arbitrary precision arithmetic libraries in programming languages. The first is arbitrary precision integer arithmetic. This allows computing with arbitrarily large integers. You can imagine these kinds of numbers as INT∞. Of course, the numbers are not really of arbitrary length but are limited by the amount of main memory installed into the system. For every practical application, however, you can imagine the resulting numbers as infinite.

A typical quality criterion for such a library is the speed and time complexity of the multiplication instruction. Classical schoolbook multiplication has a complexity of log(N)², as you have to multiply each digit of the first number with each digit of the second number. Astonishingly, there are more efficient multiplication algorithms available, the simplest being the well-known Karatsuba algorithm.

Typically the libraries for arbitrary precision integer arithmetic also offer the possibility to do some number theoretic operations, for example, prime number determination and the calculation of the GCD (greatest common divisor).

The next type of arbitrary precision numbers are arbitrary precision rational numbers.  An arbitrary precision rational number is a quotient a / b of two arbitrary precision integers. Note that every decimal number with a finite number of decimals is a rational number, for example, 1.01 = 101 / 100. For this reason, every fixed-size decimal number of type P/DEC in ABAP can be written as a rational number. For the same reason, every number of type DECFLOAT34 can also be written as a rational number, as the precision is still finite.

Rational numbers are complex in the sense that the fractions have to be shortened, for example, 2 / 4 = 1 / 2. Thus the implementation of rational numbers enforces that a good GCD algorithm is at hand.

Libraries for rational number arithmetic do not offer transcendental functions like EXP or LOG and even other simple operations such as square root. This is because the exponential and logarithm of a rational number are only also rational in very specific cases. The same is true for the square root.

For the square root, there is a simple trick though to compute arbitrary many digits with just integer arithmetic. A similar trick is not available for transcendental functions.

For the purpose of computing transcendental functions, you need a library for arbitrary precision floating point (or real number) arithmetic. These libraries can calculate real numbers with an arbitrary given precision of digits. For example, you can decide to compute the logarithm of 2 with 100, 1000, or 10000 digits.

3. Arbitrary precision arithmetic in ABAP

Up to now, ABAP had no possibility for any kind of arbitrary precision arithmetic. With the release 2308 and kernel 793, there are two new ABAP classes: CL_ABAP_BIGINT and CL_ABAP_RATIONAL for arbitrary precision integer and rational arithmetic. There is still no arbitrary precision real arithmetic exposed in ABAP although CL_ABAP_RATIONAL uses arbitrary precision real arithmetic under the hood for its conversion to DECFLOAT34.

Some methods of CL_ABAP_BIGINT

Both classes are intrusive, so if you add a number to another number you do not get a new instance but the original instance is changed. Consider the following coding:

result_bigint = bigint->add( other_bigint )

This will change the bigint instance and return a reference to self to allow chaining. So result_bigint and bigint are actually the same instance. This is done to ensure high performance. Of course, there is a clone() method that yields a copy of the bigint allowing non-intrusive operation. For example, you can write:

result_bigint = bigint->clone()->add( other_bigint )

Both classes are released for ABAP Cloud and can thus be used in Steampunk and Embedded Steampunk and SAP S/4HANA Cloud.

The class CL_ABAP_BIGINT features the following:

• Basic arithmetic operations like addition, subtraction, multiplication, and division with remainder
• Fast clone operation
• Fast multiplication
• Advanced operations like GCD and integer square root
• Number theoretic operations like prime number determination, MOD, POWMOD, and MOD_INVERSE
• Serialization to/from XML/JSON
• Conversion to external representation with thousands separator
• Shared memory enabled (non-ABAP cloud only)
• Conversion to/from STRING and to DECFLOAT34
• Released for ABAP Cloud

The class CL_ABAP_RATIONAL has nearly the same features, of course without the number theoretic functions which do not have any meaning for rational numbers.

4. How does it feel?

In this section, we want to answer the question of how it feels to operate with the new classes. Normally numeric calculations are done with integrated datatypes like DECFLOAT34 or INT8. Using classes for the same task seems unusual at first but is actually quite readable. A good example is the algorithm to compute the integer square root, i.e. floor(sqrt(n)). This would look as follows:

class compute_sqrt definition.

  public section.

    methods compute_sqrt importing number type ref to cl_abap_bigint

            returning value(sqrt) type ref to cl_abap_bigint.

endclass.

class compute_sqrt implementation.

  method compute_sqrt.

    data y type ref to cl_abap_bigint.

    final(bits) = number->get_number_of_bits( ).

    data(x) = cl_abap_bigint=>factory_from_int4( 1 )->mul_by_two_power( ( bits + 2 ) / 2 ).

    do.

      y = x->clone( )->add( number->clone( )->div( x )-quotient )->div_by_two_power( 1 ).

      if y->is_larger_or_equal( x ).

        exit.

      endif.

      x = y.

    enddo.

    return x.

  endmethod.

endclass.

start-of-selection.

  data(result) = new compute_sqrt( )->compute_sqrt(

    cl_abap_bigint=>factory_from_string( `129341967194712394612956129461294861619246` ) ).

  cl_demo_output=>display( result->to_string( ) ).

5. Available demo programs

An easy demonstration of an arbitrary precision integer library is the implementation of the RSA algorithm. RSA is a public/private key encryption which is much used. Every implementation of RSA uses large numbers with more than a hundred or a thousand digits of precision.

There is a demo class CL_DEMO_BIGINT_RSA resp. a demo report DEMO_BIGINT_RSA which generates public/private keys with a given bit-size and encrypts a small message with it. Generating RSA public/private keys in pure ABAP was impossible before.

Pure ABAP RSA implementation

There is another demo in CL_DEMO_BIGINT_SQRT and DEMO_BIGINT_SQRT to compute arbitrarily many digits of the square root of a natural number.

6. When to use arbitrary precision arithmetic?

You can use arbitrary precision arithmetic in the following cases:

• You really need large numbers with more than 34 digits because your algorithm requires it. A typical example would be the RSA algorithm.
• You have calculations with very large or very small numbers and you do not want to have any overflows or underflows. Alternatively, you have calculations with numbers of unknown size and you do not want to care about overflow or underflow.
• You have complex calculations and you do not want to care about rounding errors. Don’t forget: there are never any rounding errors for arbitrary precision arithmetic as long as you stick with the basic arithmetic operations.
• You use some number theoretic algorithms like prime number checking or modular inverse.