Вычисление числа Пи на ассемблере

[Vslav]

Нету там никакого добавления очередного члена ряда

А вот это что:

 x = 10*a[i-1] + q * i;

Имхо, это добавление переноса от умножения предыдущего разряда на 10 и деления на 2i-1.

[b2m]

думаю что перевод числа из двоичного вида в десятичное можно вынести за рамки оценки производительности алгоритма получения самого числа Пи

Есть формула, по которой считается очередная 16-ичная цифра числа Pi, т.е. фактически очередные 4 бита двоичного представления. И она не требует вычисления предыдущих цифр. Проблема только в том, что чтобы перевести бинарное число в десятичное, нужно много раз умножать на 10 всё число целиком. Т.е. от наличия дополнительных цифр в двоичном числе зависят цифры в десятичном представлении этого числа. А после перевода первых N цифр в десятичный вид уже нельзя добавить новые двоичные данные.

Получается, сначала нужно рассчитать все цифры 16-ичного (двоичного) числа, и только потом заняться переводом его в десятичное. Для 8-мибитного компьютера перевод двоичного числа в десятичный вид не менее трудоёмок (в плане времени вычисления), чем рассчёт каких либо других формул.

- - - Добавлено - - -

А вот это что:

 x = 10*a[i-1] + q * i;

Имхо, это добавление переноса от умножения предыдущего разряда на 10 и деления на 2i-1.

a[i] это цифра в другом счислении. Понятно, что умножая это число на 10 нужно учитывать ещё и перенос из другого разряда. Очередной множитель цифры этой системы сисления как раз равен i/(2*i-1), а q, как ты правильно заметил - это перенос. Просто умножение на i в одной строке, а деление - в другой.

[Vslav]

Забавно, получается что:

for(j=0;j<LEN;j++) a[j]=2;

просто задает число пи равное 2.222222...., а все остальное ниже - просто перевод в десятичную систему? А в какой системе исчисления пи равно 2.222...?

[b2m]

Тут надо читать про spigot-алгоритм вычисления числа pi:

[Vslav]

А, тогда не совсем позиционная система исчисления (что предполагает фиксированное основание), а все-таки обычный ряд. Просто тут его вычисление удачно совместили с переводом в десятичную систему. А в массиве находятся не цифры, а обновляемые члены ряда.

Update: кстати, добавление нового члена ряда прикольно сделано, с отложенным переносом. Если новая полученная цифра не девятка, то переноса в предыдущую цифру не предполагается (неочевидно, как по мне - требует доказательства, но ладно), значит предыдущую цифру можно вывести. А если девятка - то копим число девяток подряд, вдруг произойдет перенос и его распространение.

[ivagor]

Очередная и, надеюсь, последняя версия spigota - pirk20.zip
100 знаков - 19897238 тактов - 11.19 сек (это с расчетом таблицы!)
535 знаков - 551337754 тактов - 5 мин 10 сек
Обращаю внимание, что запускать нужно G4200
Можно еще чуть-чуть ускорить, если размещать таблицу для умножения с 0000h, но я не стал заниматься крохоборством.

[Advertiser]

[b2m]

Ну, молодец, молодец, ускорил в 5 раз
Теперь напиши это на псевдоассемблере и ещё ассемблер, генерирующий прогу для любого из компов, что есть у меня в эмуляторе

[ivagor]

[/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]

[Vslav]

который используется в сишном варианте по ссылке очень похож на spigot, но, если я правильно понимаю, переводит не по одной цифре, а по 4.
[/sarcasm detection on]

А это и есть тот же spigot только переводит в систему с основанием 10000. Ну и массив 32-битный, чтобы не переполнялись члены. Кстати, возможно, там ошибка - если будет 9999 и перенос из следующего разряда. Вероятность небольшая, но пи - число иррациональное и трансцендентное , в нем все комбинации группы цифр рано или поздно встретятся.

Теперь напиши это на псевдоассемблере и ещё ассемблер, генерирующий прогу для любого из компов, что есть у меня в эмуляторе

LLVM с его IR (intermediate representation, по факту это псевдоассемблер), возможно "спасет отца русской демократии"

[ivagor]

Кстати, возможно, там ошибка

Из интереса посчитал той программкой 1600 знаков - все ОК, т.е. по крайней мере в этом районе все нормально.
На i5 показывает время расчета в районе сотых долей секунды, насколько все же далеко вперед ушло развитие процессоров.