Fast arbitrary-precision logarithms with bcmath

mpen

Here's what I've got

function bcln($n, $scale=10) {
    $iscale = $scale+3;
    $result = '0.0';
    $i = 0;

    do {
        $pow = (1 + (2 * $i++));
        $mul = bcdiv('1', $pow, $iscale);
        $fraction = bcmul($mul, bcpow(bcsub($n, '1', $iscale) / bcadd($n, '1.0', $iscale), $pow, $iscale), $iscale);
        $lastResult = $result;
        $result = bcadd($fraction, $result, $iscale);
    } while($result !== $lastResult);

    return bcmul('2', $result, $scale);
}

But this takes 5.7 seconds to run bcln(100) (natural log of 100, 10 decimal places). Furthermore, it's not always accurate for more decimal places. Is there a better algorithm?

For that specific run, it takes 573 iterations to settle on the result.

Matthew Slyman

Do you require an arbitrary-length string as an answer? Or do you require arbitrary precision, or arbitrary exponent size? Or… would a double-precision floating-point answer (return-value) suffice; given that we're "only" working with the logarithm of a number of "arbitrary" size?

Double precision floating point numbers have an 11-bit signed exponent: therefore, if your big number string has a length of ≤1022 bits ≈ 307 decimal digits (so string length of 306 characters including the decimal point), you are safe! More accurately, you should be safe if the absolute value of the resulting decimal exponent is ≤307. Do you need bigger exponents than that? (I suppose in other words: are you working with real-world numbers or theoretical/ pure mathematics?)

Why not just use some string processing, along with some simple floating-point log arithmetic? This should be very fast, for any real-world numbers…

function bclog10($n){
    //←Might need to implement some validation logic here!
    $pos=strpos($n,'.');
    if($pos===false){
        $dec_frac='.'.substr($n,0,15);$pos=strlen($n);
    }else{  $dec_frac='.'.substr(substr($n,0,$pos).substr($n,$pos+1),0,15);
    }
    return log10((float)$dec_frac)+(float)$pos;
}

You can convert the base using some well-known log arithmetic:

function bclogn($n,$base=M_E){//$base should be float: default is e
    return bclog10($n)*log(10)/log($base);
}

I have tested these functions and they work for me, for the examples I supplied; giving exactly the same answers as the Windows 10 calculator, up to the limits of double-precision arithmetic as used by PHP.

If you actually need more than 15 digits of precision and more than 307 for the decimal exponent, you might be able to implement your own "BigFloat" class object, and somehow build its methods out of the standard built-in floating-point functions using a divide-and-conquer approach! Then perhaps, we might use that as the basis of an arbitrary-precision floating-point logarithm algorithm, by combining this with the functions/techniques described above. You might want to consider consulting with the people at math.stackexchange.com, to find out more about whether this could be a feasible approach.

MAJOR EDIT: 2nd attempt…

function bclog10($n){//By Matthew Slyman @aaabit.com
    $m=array();// ↓ Validation, matching/processing regex…
    preg_match('/^(-)?0*([1-9][0-9]*)?(\.(0*))?([1-9][0-9]*)?([Ee](-)?0*([1-9][0-9]*))?$/',$n,$m);
    if(!isset($m[1])){throw new \Exception('Argument: not decimal number string!');}
    $sgn=$m[1];if($sgn==='-'){throw new \Exception('Cannot compute: log(<⁺0)!');}
    $abs=$m[2];$pos=strlen($abs);
    if(isset($m[4])){$fre=$m[4];}else{$fre='';}$neg=strlen($fre);
    if(isset($m[5])){$frc=$m[5];}else{$frc='';}
    if(isset($m[7])){$esgn=$m[7]==='-'?-1:1;}else{$esgn=1;}
    if(isset($m[8])){$eexp=$m[8];}else{$eexp=0;}
    if($pos===0){
        $dec_frac='.'.substr($frc,0,15);$pos=-1*$neg;
    }else{  $dec_frac='.'.substr($abs.$fre.$frc,0,15);
    }
    return log10((float)$dec_frac)+(float)$pos+($esgn*$eexp);
}

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

From Dev

LLVM arbitrary precision integer

From Dev

Python mpmath not arbitrary precision?

From Dev

LLVM arbitrary precision integer

From Dev

Fixed precision vs. arbitrary precision

From Dev

arbitrary floating precision number to string

From Dev

"Multiplication of Arbitrary Precision Numbers" in Scheme

From Dev

stripe node arbitrary precision number

From Dev

fast double multiplication with integer precision

From Dev

Arbitrary precision for decimals square roots in golang

From Dev

postgresql date_trunc to arbitrary precision?

From Dev

Arbitrary precision arithmetic with very big factorials

From Dev

Is Python incorrectly handling this "arbitrary precision integer"?

From Dev

Arbitrary precision arithmetic with very big factorials

From Dev

Calculate Pi with arbitrary precision digit by digit

From Dev

BBP-Algorithm in Python - Working with Arbitrary-precision arithmetic

From Dev

Calculating pi without arbitrary precision and only basic arithmetic

From Dev

Which programming languages have arbitrary precision floating-point literals?

From Dev

Is it possible to achieve arbitrary-precision arithmetic with no rounding issues in JavaScript?

From Dev

Hash an arbitrary precision value (boost::multiprecision::cpp_int)

From Dev

arbitrary precision linear algebra c/c++ library with complex numbers

From Dev

Arbitrary pre-set precision decimals (Almost like BigDecimal)

From Dev

String format double with arbitrary precision, fixed decimal position

From Dev

Calculating pi without arbitrary precision and only basic arithmetic

From Dev

Fast arbitrary distribution random sampling (inverse transform sampling)

From Dev

Fast, unbiased, integer pseudo random generator with arbitrary bounds

From Dev

Fast arbitrary distribution random sampling (inverse transform sampling)

From Dev

Fast, unbiased, integer pseudo random generator with arbitrary bounds

From Dev

Fast vectorized rsqrt and reciprocal with SSE/AVX depending on precision

From Dev

fast computation for extended precision floating point for number theory application

Related Related

  1. 1

    LLVM arbitrary precision integer

  2. 2

    Python mpmath not arbitrary precision?

  3. 3

    LLVM arbitrary precision integer

  4. 4

    Fixed precision vs. arbitrary precision

  5. 5

    arbitrary floating precision number to string

  6. 6

    "Multiplication of Arbitrary Precision Numbers" in Scheme

  7. 7

    stripe node arbitrary precision number

  8. 8

    fast double multiplication with integer precision

  9. 9

    Arbitrary precision for decimals square roots in golang

  10. 10

    postgresql date_trunc to arbitrary precision?

  11. 11

    Arbitrary precision arithmetic with very big factorials

  12. 12

    Is Python incorrectly handling this "arbitrary precision integer"?

  13. 13

    Arbitrary precision arithmetic with very big factorials

  14. 14

    Calculate Pi with arbitrary precision digit by digit

  15. 15

    BBP-Algorithm in Python - Working with Arbitrary-precision arithmetic

  16. 16

    Calculating pi without arbitrary precision and only basic arithmetic

  17. 17

    Which programming languages have arbitrary precision floating-point literals?

  18. 18

    Is it possible to achieve arbitrary-precision arithmetic with no rounding issues in JavaScript?

  19. 19

    Hash an arbitrary precision value (boost::multiprecision::cpp_int)

  20. 20

    arbitrary precision linear algebra c/c++ library with complex numbers

  21. 21

    Arbitrary pre-set precision decimals (Almost like BigDecimal)

  22. 22

    String format double with arbitrary precision, fixed decimal position

  23. 23

    Calculating pi without arbitrary precision and only basic arithmetic

  24. 24

    Fast arbitrary distribution random sampling (inverse transform sampling)

  25. 25

    Fast, unbiased, integer pseudo random generator with arbitrary bounds

  26. 26

    Fast arbitrary distribution random sampling (inverse transform sampling)

  27. 27

    Fast, unbiased, integer pseudo random generator with arbitrary bounds

  28. 28

    Fast vectorized rsqrt and reciprocal with SSE/AVX depending on precision

  29. 29

    fast computation for extended precision floating point for number theory application

HotTag

Archive