What other classes could go in the Numbers namespace?

[Beakerboy]

I was mulling over this question in my head today. Do you foresee any future need for a rational number class? If a user would want to do calculations with numbers and not have to worry about floating point errors, a class could be created with three integer properties, one for the whole number, and two for the fractional part. We could define all the algebraic functions to work on rational numbers, and reduce the fraction after each calculation to keep them from growing.

Any other number classes you can think of?

[markrogoyski]

One thing I was thinking of was an Imaginary number class that would inherit from Complex (r is always 0). Then maybe define Arithmetic::sqrt() that would work on negative numbers.

The main reason I moved Complex to a Number namespace was the duplication in the namespace and class name. Just a naming convention thing--no grand plans associated with it.

The rational number class might be interesting if someone wants to use it in isolation, but just like the Complex class, I'm not sure how to integrate that in to work with other functions without making a giant spaghetti conditional mess.

[TheFausap]

Quaternions... Octonions... :-D

[Beakerboy]

@TheFausap Feel free to copy the layout used in the complex number class to implement these if you would like. As stated in the other thread, if they follow the same function format then it should be a breeze to create matrixes using these other data structures.

[TheFausap]

@Beakerboy I could try :-)

[Beakerboy]

@TheFausap I have a Quaternion class in the works in case this is something you are honestly interested in: https://github.com/Beakerboy/math-php/blob/Quaternion/src/Number/Quaternion.php

[TheFausap]

@Beakerboy I already wrote the class, with some light differences with yours. Sorry if I didn't post earlier. I'll start with your file, merging with mine, if for you is ok.

[TheFausap]

@Beakerboy https://github.com/TheFausap/math-php/blob/master/src/Number/quaternion.php

I have to complete the tostring function, dealing with the imaginary units (all the permutations). But you already did it :-)

[Beakerboy]

My ToString function is not correct. It would produce a string like "1 + -2i + 5k", where each value will have a "+" before it.

Write up a series of unit tests and submit it to @markrogoyski as a pull request. Thanks for the help.

[Beakerboy]

Also, if you add "implements ObjectArithmetic" after the class declaration you will soon be able to use Quarternions as elements in a Matrix. You will have to merge the recent changes from the main development branch into your repository first.

[Beakerboy]

Would a BigInt class be useful for general mathematical use?

[markrogoyski]

What would be the purpose of BigInt? Is it to represent an integer beyond the \PHP_INT_MAX size so it does not convert to a float?

For reference, on a 64-bit machine:

php > echo PHP_INT_MAX;
9223372036854775807
php > echo PHP_INT_MAX * PHP_INT_MAX * PHP_INT_MAX * PHP_INT_MAX * PHP_INT_MAX * PHP_INT_MAX;
6.1565634681866E+113

[Beakerboy]

Yes, it's for precise large numbers, avoiding floating point errors.

[markrogoyski]

9,223,372,036,854,775,807 seems pretty large =)

I'm not sure how it would be used, just like I'm not sure how complex numbers can be used else where in the library at this point. So, I think long-term with infinite development resources, sure. But in the short term, I'm not sure how useful it would be if it isn't easily used elsewhere in the library. If you have some design ideas let me know.

Also, you might investigate what others do for this, as there are some other projects that provide this functionality. Do they have a way to make the BitInt class useful when every other math function expects a regular scalar type.

[Beakerboy]

Bigints are used in cryptography and prime number work. It might be nice to just have them here for users.

[Beakerboy]

I brought it up after seeing this in PEAR: http://pear.php.net/package/Math_BigInteger/docs/1.0.0RC3/Math_BigInteger/Math_BigInteger.html

[markrogoyski]

Good point about prime numbers in relating to cryptography. That's definitely an important use case for a BigInt.

[Beakerboy]

I've been working on adding in the function that calculates the constants used in the gammaLanczos method. (https://github.com/Beakerboy/math-php/blob/Lanczos/src/Functions/Support.php). I think this is another case where BigInt and/or BigFloat objects would be useful. I'll have to dig into it some more, but I think floating point errors are preventing the constants from being calculated accurately enough. Most are fine, but a couple are almost 10% off. A few algorithms online specifically use Big numbers for their calculation, then convert to standard floats for final presentation and use.

[markrogoyski]

A BigInt type of number class seems useful for many different kinds of applications. Do you have an idea of what the design of this class would look like and how it would be used?

[Beakerboy]

https://github.com/Beakerboy/math-php/blob/BigInt/src/Number/BigInt.php

The internal representation is handled by two ints, and the bit format is in standard signed format, 2s compliment when negative. This way, standard bitshift division and multiplication is possible.

[Beakerboy]

Would you prefer the bigint object be 128 bits or twice as large as the standard int. On a 32 bit OS, the object would require 4 ints to be 128 bits.

[markrogoyski]

It definitely needs to be larger than 64 bit, as that is what you get on a modern system. Most systems are 64-bit these days, so does it make sense to develop something new considering what makes sense on a 32-bit machine? 128-bit seems reasonable. Does it need to be larger than that to effectively work with cryptography and prime number factorization, for instance?

[Beakerboy]

I guess I'll restate the question, if the class contains an array of two ints, then that would give access to a 64-bit number to somebody who is running 32-bit architecture. For somebody on a more modern system they would be able to do 128 bit arithmetic. The alternative is to guarantee 128 bit size on the object which would require detecting whether the user is operating 32 bit architecture or 64-bit architecture and operating on the array accordingly. This means having an array of either two or four ints.

I think another route is an arbitrary precision int, where the size of the array keeps growing as needed. Before tackling this, I think it would be good having methods that work on fixed-size arrays. As far as crypto goes, SHA256 would require a 256 bit number.

[Beakerboy]

If a BigInt overflows, do you think it should throw an exception, or should it be converted into a BigFloat

[markrogoyski]

If you are working with a BigInt, and the expectation of an arithmetic operation is to return a BigInt, if you get into a situation where that cannot happen, it seems like that is an exceptional situation and would warrant an exception being thrown. The class's API is BigInts go in, BigInts come out, right? Throwing an exception seems like the right choice.

[Beakerboy]

The reason I ask is that in the case of a native integer, multiplying two large integers will produce a float. I guess there could be a separate method that would produce a bigfloat if needed.

[Beakerboy]

It looks like the Travis-CI PHP package includes bcmath by default. I’ve started to make a wrapper for the arbitrary precision numbers in Math-PHP. However, this would require users have a PHP 7 installation with bcmath included...which is not difficult with package managers. https://github.com/Beakerboy/math-php/tree/bcmath

Any thoughts? Again, arbitrary precision numbers could help some of our “slow to converge” algorithms like the regularized incomplete beta and the gamma function. I’m pretty sure both of these have summations that can get very large very fast. Also, prime numbers and crypto. I was wanting to use it to enable users to use the Lanczos gamma function with other values for g and n if they wanted.

[markrogoyski]

One of my goals with MathPHP is to make it easy to use. One way to make it easy to use is to not require any external dependencies. Just composer require it and you are ready to go.

As soon as you have installation instructions that look like this:

# Requires BCMath PHP extension
# For Debian distributions
sudo apt install php7.0-bcmath

# For Redhat distributions
yum install php-bcmath

# For Mac
Install homebrew (some link goes here)
Some homebrew command goes here

# For Windows
Some link goes here.

# Enable PHP extension
Then enable the PHP extension by setting --enable-bcmath

.. Other stuff

You've basically lost 80% of your potential user base. They are not going to figure out how to use your library if it requires work on their part. They'll just implement their own standard deviation function, and probably get it wrong.

So, if the BCMath extension is something you want to use, I'd like it to still work even if the extension is not installed. Maybe you can use extension_loaded and have a fallback implementation if bcmath is not there.

Let me know if you need any help trying to figure out how to make it all work. I imagine unit testing both implementations might be tricky.

[Beakerboy]

My motivation for this is with our use of a predefined array of Lanczos constants in the gamma function. In an ideal world, this library should be able to calculate those constants, right? Currently it does not work, due to a combination of overflow errors and rounding errors. I am hoping that the use of arbitrary precision numbers will allow it to work. Then I plan on adding a unit test to prove that the library calculates the literature values properly.

[Beakerboy]

I'm going to change the BigInt to use strings instead of arrays as the internal representation. The advantage is, the CPU will not matter, and the "number" can be arbitrarily large. Here's an example of a divide function:

/**
     * Abitrary precision, arbitrary base integer division
     *
     * Each character in each string is a digit in a particular base system.
     * The value of the digit is the ascii code of the digit.
     *
     * Since the character "0" has ASCII code 48, we can set an offset of 48
     * example longDivide("127", "3", 10, "0") = "42"
     *
     * With a different offset
     * longDivide("BCH", "D", 10, "A") = "42"
     *
     * As raw binary data, since "~" has ascii code 126:
     * longdivide("~", char(3)) = 42
     */
    protected static function longDivide(string $dividend, string $divisor, int $base = 256, string $offset = ""): array
    {
        $length = strlen($dividend);
        $mod = 0;
        $int = "";
        $remove_leading_zero = true;
        for ($i = 0; $i < $length; $i++) {
            $place_value = ord($dividend[$i]) - ord($offset) + $base * $mod;
            if (!$remove_leading_zero || !$place_value == 0) {
                $step_int = chr(intdiv($place_value, ord($divisor) - ord($offset)) + ord($offset));

                // Don't add new leading zeros.
                if (!$remove_leading_zero || $step_int !== $offset) {
                    $int .= $step_int;
                }
                $mod = $place_value % (ord($divisor) - ord($offset));
                $remove_leading_zero = false;
            }
        }
        return [$int, chr($mod + ord($offset))];
    }

The way this is written, a user can divide two strings in any base, so if you have a string of base 10 numbers, and want to divide them, you can do:

$a = "782318762387431876123789623189762138974612389762891764358192765489716258972461";
$b = "9834759375";
list($int, $mod) = longDivide($a, $b, 10, "0");
echo $int  . " remainder " . $mod;
// prints "86924306931936875124865513687751348774956932195876862706465862832190695441384 remainder 5"

// or if you have binary (raw) data, you can use base 256:
list($int, $mod) = longDivide("e", "2"); // ord("e") = 101, and ord(2) = 50
echo ord($int)  . " remainder " . ord($mod);  // prints "2 remainder 1"

[Beakerboy]

As a side note... I wrote this function to convert raw 256 bit bitcoin extended public key hashes to the standard 58-bit Wallet Import Format, for a different project.

[Beakerboy]

Arbitrary Integers have been merged