Есть формула, по которой считается очередная 16-ичная цифра числа Pi, т.е. фактически очередные 4 бита двоичного представления. И она не требует вычисления предыдущих цифр. Проблема только в том, что чтобы перевести бинарное число в десятичное, нужно много раз умножать на 10 всё число целиком. Т.е. от наличия дополнительных цифр в двоичном числе зависят цифры в десятичном представлении этого числа. А после перевода первых N цифр в десятичный вид уже нельзя добавить новые двоичные данные.
Получается, сначала нужно рассчитать все цифры 16-ичного (двоичного) числа, и только потом заняться переводом его в десятичное. Для 8-мибитного компьютера перевод двоичного числа в десятичный вид не менее трудоёмок (в плане времени вычисления), чем рассчёт каких либо других формул.
- - - Добавлено - - -
a[i] это цифра в другом счислении. Понятно, что умножая это число на 10 нужно учитывать ещё и перенос из другого разряда. Очередной множитель цифры этой системы сисления как раз равен i/(2*i-1), а q, как ты правильно заметил - это перенос. Просто умножение на i в одной строке, а деление - в другой.
Забавно, получается что:
просто задает число пи равное 2.222222...., а все остальное ниже - просто перевод в десятичную систему? А в какой системе исчисления пи равно 2.222...?Код:for(j=0;j<LEN;j++) a[j]=2;
Тут надо читать про spigot-алгоритм вычисления числа pi:
А, тогда не совсем позиционная система исчисления (что предполагает фиксированное основание), а все-таки обычный ряд. Просто тут его вычисление удачно совместили с переводом в десятичную систему. А в массиве находятся не цифры, а обновляемые члены ряда.
Update: кстати, добавление нового члена ряда прикольно сделано, с отложенным переносом. Если новая полученная цифра не девятка, то переноса в предыдущую цифру не предполагается (неочевидно, как по мне - требует доказательства, но ладно), значит предыдущую цифру можно вывести. А если девятка - то копим число девяток подряд, вдруг произойдет перенос и его распространение.
Последний раз редактировалось Vslav; 09.11.2015 в 12:54.
Очередная и, надеюсь, последняя версия spigota - pirk20.zip
100 знаков - 19897238 тактов - 11.19 сек (это с расчетом таблицы!)
535 знаков - 551337754 тактов - 5 мин 10 сек
Обращаю внимание, что запускать нужно G4200
Можно еще чуть-чуть ускорить, если размещать таблицу для умножения с 0000h, но я не стал заниматься крохоборством.
Последний раз редактировалось ivagor; 09.11.2015 в 13:00. Причина: добавил такты
С любовью к вам, Yandex.Direct
Размещение рекламы на форуме способствует его дальнейшему развитию
Ну, молодец, молодец, ускорил в 5 раз
Теперь напиши это на псевдоассемблере и ещё ассемблер, генерирующий прогу для любого из компов, что есть у меня в эмуляторе
[/sarcasm detection off]
А тебя не смущает, что по ссылке, которую приводил litwr, программа на си считает 800 знаков за 1,458,354,526 тактов? Если попробовать сравнить, то 535 знаков она посчитала бы примерно за 1,458,354,526/2,2=662888420 тактов. Т.е. сейчас программа на асме 8080 наконец-то стала считать быстрее программы на си для z80. Как то не очень круто, если учесть, что в той проге используются и 32 битные операции. Алгоритм, который используется в сишном варианте по ссылке очень похож на spigot, но, если я правильно понимаю, переводит не по одной цифре, а по 4.
[/sarcasm detection on]
А это и есть тот же spigot только переводит в систему с основанием 10000. Ну и массив 32-битный, чтобы не переполнялись члены. Кстати, возможно, там ошибка - если будет 9999 и перенос из следующего разряда. Вероятность небольшая, но пи - число иррациональное и трансцендентное , в нем все комбинации группы цифр рано или поздно встретятся.
LLVM с его IR (intermediate representation, по факту это псевдоассемблер), возможно "спасет отца русской демократии"
Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)