Быстрые логарифмы произвольной точности с bcmath

Вот что у меня есть

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);
}

Но для запуска bcln(100) требуется 5,7 секунды (натуральный логарифм 100, 10 знаков после запятой). Кроме того, это не всегда точно для большего количества знаков после запятой. Есть ли лучший алгоритм?

Для этого конкретного прогона требуется 573 итерации, чтобы получить результат.


person mpen    schedule 24.07.2014    source источник
comment
Я не уверен, что это тот ответ, который вы ищете, но родной log() возвращает тот же результат практически мгновенно...   -  person scrowler    schedule 25.07.2014
comment
@scrowler Вы, должно быть, пропустили часть о произвольной точности.   -  person mpen    schedule 25.07.2014
comment
Да, я просто сравнил результаты. Возможно, вы могли бы посмотреть, как сократить итерации вашего цикла...   -  person scrowler    schedule 25.07.2014
comment
@scrowler Чем больше я уменьшаю итерации, тем менее точным он становится. Мне нужен другой алгоритм, который сходится быстрее.   -  person mpen    schedule 25.07.2014


Ответы (1)


Вам нужна строка произвольной длины в качестве ответа? Или вам нужна произвольная точность или произвольная экспонента? Или… будет достаточно ответа с плавающей запятой двойной точности (возвращаемое значение); учитывая, что мы "только" работаем с логарифмом числа "произвольного" размера?

Числа с плавающей запятой двойной точности имеют 11-битную экспоненту со знаком: поэтому, если ваша строка больших чисел имеет длину ≤1022 бита ≈ 307 десятичных цифр (то есть длина строки 306 символов, включая десятичную точку), вы в безопасности! Точнее, вы должны быть в безопасности, если абсолютное значение результирующего десятичного показателя степени ≤307. Вам нужны более высокие показатели, чем это? (Я полагаю, другими словами: вы работаете с реальными числами или с теоретической/чистой математикой?)

Почему бы просто не использовать обработку строк вместе с простой логарифмической арифметикой с плавающей запятой? Это должно быть очень быстро для любых реальных чисел…

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;
}

Вы можете преобразовать базу, используя хорошо известную логарифмическую арифметику:

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

Я протестировал эти функции, и они работают для меня, для примеров, которые я предоставил; дает точно такие же ответы, как калькулятор Windows 10, вплоть до пределов арифметики двойной точности, используемой PHP.

Если вам на самом деле нужно более 15 цифр точности и более 307 для десятичной экспоненты, вы можете реализовать свой собственный объект класса «BigFloat» и каким-то образом построить его методы из стандартных встроенных функций с плавающей запятой, используя принцип «разделяй и властвуй»! Затем, возможно, мы могли бы использовать это как основу алгоритма логарифмирования с плавающей запятой произвольной точности, объединив это с функциями/методами, описанными выше. Возможно, вы захотите проконсультироваться с людьми на math.stackexchange.com, чтобы узнать больше о том, возможен ли такой подход.

БОЛЬШОЕ ИЗМЕНЕНИЕ: вторая попытка…

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);
}
person Matthew Slyman    schedule 30.10.2015
comment
Реальный мир хорош. Это входит в библиотеку PHP общего назначения, поэтому чем больше чисел я могу поддерживать, тем лучше, но не за счет огромных затрат на производительность. Сейчас попробую вашу реализацию. - person mpen; 31.10.2015
comment
Ваша реализация вообще не работает. bclog10(100) дает 6.0 вместо 2. - person mpen; 31.10.2015
comment
Я заметил еще одну серьезную ошибку: вводите числа вроде 0,000025 — легко понять, почему это не сработает. Я работаю над исправлением этого прямо сейчас и также проверю ваш пример. - person Matthew Slyman; 31.10.2015
comment
Я имею в виду, конечно, такие числа, как 0,0000000000000000000000000000025… Нам нужно немного больше поработать со строковой обработкой, прежде чем мы начнем полагаться на встроенные функции с плавающей запятой. Я исправляю это сейчас... В вашем примере, bclog10(100), была простая ошибка на стороне $pos===false... - person Matthew Slyman; 31.10.2015
comment
Я опубликовал свою вторую попытку сейчас, и, похоже, она решает проблемы, которые мы выявили в первой версии (а также включает улучшенную логику проверки в качестве побочного продукта необходимой дополнительной обработки строк). Жду результатов вашего тестирования! Под какими лицензиями вы выпускаете свою библиотеку PHP? В зависимости от вашего ответа, условий и обычаев StackOverflow; Я мог бы снять ограничения с моей декларации CC, которую я хотел бы включить, если вы не возражаете. Просто оставить строку комментария нетронутой в исходном коде в любом случае достаточно для атрибуции. - person Matthew Slyman; 31.10.2015
comment
p.s. Пункт CC-SA не означает, что вы должны делиться/опубликовывать весь исходный код. Просто любые обновленные версии этой функции. С нетерпением ждем ваших отзывов! - person Matthew Slyman; 31.10.2015
comment
Моя библиотека выпущена в рамках MIT. Я не буду добавлять к нему никаких ограничений. - person mpen; 31.10.2015
comment
Ваша функция начинает ломаться для больших чисел: bclog10('43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875') дает 208.63815524781 вместо 183.638155247810724. Это работает для 280571172992510140037611932413038677189525, но даже встроенный log справится с этим. - person mpen; 31.10.2015
comment
Я просто ввел это длинное число в Microsoft Word и провел подсчет слов. Он имеет 209 цифр. Поэтому я думаю, что моя функция дает вам правильный ответ, а не другая ваша функция, которую вы используете для сравнения! - person Matthew Slyman; 31.10.2015
comment
Лицензия MIT подойдет. Я доволен чем-либо с достаточно открытым исходным кодом (на самом деле, он не становится более открытым, чем сам StackExchange), и я рад, что вы выпускаете свой другой код под лицензией MIT. - person Matthew Slyman; 31.10.2015
comment
Я использовал WolframAlpha для проверки, но я думаю, что вы можете быть правы - мой ввод, должно быть, был отключен. Вместо этого попробовал с Python — похоже, вы были правы. Извини :D - person mpen; 02.11.2015
comment
StackOverflow: алгоритм log() произвольной точности — это выглядит интересно , хотя я считаю, что мой подход использует встроенные функции журнала, поддерживаемые таблицами журнала с двойной точностью (быстрый поиск в ПЗУ), встроенными в микропроцессор! Чтобы идеально ответить на ваш первоначальный вопрос (произвольная точность, действительно произвольный размер); нам понадобится класс BigFloat с переменными-членами произвольного размера для мантиссы/экспоненты и методы, реализующие алгоритм, подобный этому! - person Matthew Slyman; 02.11.2015
comment
Я только что обновил функцию, чтобы обрабатывать научную нотацию в качестве альтернативного формата ввода. - person Matthew Slyman; 05.11.2015