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

[litwr]

оптимизации для лишь для 100 цифр

Мелко как-то, даже Командор 64 с текущим алгоритмом почти 5000 знаков может считать. Это машина класса Вектора.
Что-то вы странное про си написали. На нём библиотеки пишут для всяких питонов и сами питоны. На ассемблере тольку управление памятью и ввод-вывод с железом.
Данные для SuperCPU - довольно массовой (10-и тысяч) приставки из 90-х. А Хамелеон это продолжение разработки уже почти легендарной компьютерной девушки Джерри - это уже 21 век, разработка продолжается. Можно воткнуть в C64, а можно в него воткнуть usb-клавиатуру.- https://icomp.de/shop-icomp/en/produ...meleon_64.html

Мое мнение насчет разделения расчета и вывода на экран - это нормально только для расчета 100 цифр.

Таким мнением вы внесли в тему политику, поиск преференций для выбранной платформы.

Можно сделать версию для cp/m

Уже выложил такую для final-precise. А универсального способа работы с таймером в ср/м нет, нужно подстраиваться под каждый случай. В выложенной версии используются обращения к фирменным ROM-вызовам.

[b2m]

Таким мнением вы внесли в тему политику

Непротрезвел что-ли? Какая тут политика? Совсем обалдели...

[perestoronin]

Непротрезвел

До 10го мало кто из коллег будет трезвым (я не в счет, т.к. "его" не пью), не пьют лишь только убежденные трезвенники и язвенники. Но среди непьющих % в последние годы выше тех, кто не пьёт по убеждению и это не может не радовать меня.
А на счет преференций, так оно так все и делается, нужно продвигать отечественную продукцию, а её в Митино очень много и не дороже чем по 30 руб за микросхему КР580ВМ80А.
Зачем нам Коммодоры и Эпплы 1, когда у нас и КР580ВМ80А не до конца прокачан ? Не у всех есть лишние ресурсы по времени чтобы заниматься сразу несколькими архитектурами, да и не всем оно по большому счету нужно. Но это не значит что нам не интересно что творится в плане войны с числом Пи у них там, интересны сводки с фронта Коммодора и Эппла, но желательно не отсыл на сайты с ихними кракозябрами, которые даже гуглопереводчик не может правильно и понятно перевести, а выжимки сюда в тему с циферками на русском языке, для простоты можно присылать краткое описание новизны алгоритмов и достигнутые улучшения подкрепленные полученными сек за 100 знаков.

100 знаков нам пока за глаза достаточно для начала опытов и поиска решения позволяющего перешагнуть за 1 сек для 100 знаков числа Пи на КР580ВМ80А при его штатных частотах (без разгона).

[ivagor]

100 - 2.7568 сек
1000 - 280.9320 сек - 4 мин 40.9320 сек

[perestoronin]

почти 5000 знаков может считать

А Phenom то может посчитать сколько циферок! Главное чтобы места на жестком диске в 4Тбайта для результата было
А теперь вернемся к нашим баранам, т.е. к 100 циферкам и удобному, для поиска слабых мест в примитивных алгоритмах, процессору КР580ВМ80А, коих полно у каждого, не то, что экзотичные в наших краях иностранцы, интересно коим боком их заносит под Москву ? Ну не каждому дано владеть разными машинками Тюринга и Поста.
Технарям попроще ставить эксперименты именно на простых процессорах - типа проверенных временем и к тому же по прежнему доступных КР580ВМ80А и КР1858ВМ*.
Но за циферки все равно спасибо, впрочем и за Си с Бейсиками тоже. Вот еще бы кто на Форте поупражнялся в скорости расчета числа Пи

[blackmirror]

Если spigot'а перевернуть, то есть внутренним циклом проходить по переносам(от старших к младшим), а внешним по множителям/делителям(в убывающем направлении), то понадобится только массив переносов. При вычислении по 4 цифры переносы будут меньше 10000*2, и хранить потребуется 1000/4*2=500 байт. На каждой итерации внешнего цикла можно сгенерировать оптимальный код для внутреннего, поскольку там требуется только умножение/деление на константу. Вычислений здесь меньше конечно не станет, но не понадобится делать CALL/RET, насиловать стек, да и искать процедуру по таблице. После завершения внешнего цикла, нужно еще раз пройтись по переносам, приводя их к диапазону до 10000, и увеличивая соседний если нужно. Никаких "недействительных" цифр здесь не будет, если двигаться от младших к старшим. Если сделать процедуры умножения/деления 16x24->40, 40/24->16_24, то можно будет вычислять хоть 100К цифр, сейчас это конечно смысла не имеет, но 20 лет назад вычислить 100К цифр при 64К памяти было бы неплохо, пусть даже и за несколько месяцев.

spigot.txt

Сумма вычисляется по формуле s=s*10000+p[i]*a, затем это делится на b. Поскольку a и b во внутреннем цикле можно считать константами, то возможно получится одновременно умножать на 10000 и делить на b, не вылезая за пределы 16 бит. По крайнем мере в той ветви алгоритма где делитель прибавляется, можно сначала добавить множитель, и если результат станет положительным, значит на данном шаге делитель нужно вычитать. Оптимизация здесь возможна за счёт того, что сдвиг суммы станет общим для умножения и деления, и вроде как не потребуется подгружать младшие байты для следующих итераций. А вот про p[i] можно сразу сказать, что частное будет равно 0, поскольку a<b, и вычислять нужно только остаток. Но эти идеи еще нуждаются в проверке.

[Advertiser]

[ivagor]

Интересный подход. Если честно - я не осмыслил, как это работает, но попробовал. Выложенный вариант начиная с 4934 цифры считает неправильно (последние правильные цифры - 3096, потом д.б. 3408).

[blackmirror]

ivagor, это я неправильно константы объявил, должно быть:
// const unsigned D=4,N=4936u,M=2*N*3322u/1000u;
const unsigned D=4, M=32767u, N=M/2*1001u/3322u;
сначала M было максимальным множителем, потом решил что для делителя нагляднее какой точности нужны процедуры умножения/деление, а константы переделать забыл. Вообще количество итераций внешнего цикла примерно равно требуемой длине в битах, если её умножить на lg(2), то как раз получается количество цифр. Остатки которые нужно хранить в массиве не превышают 2*10^n, где n - количество цифр в блоке. Ну а сумма перед делением может в M раз быть больше чем остаток. То есть 2*M*10^n должно влезать в сумму без переполнения. Если сумма 32 разряда, то считая по 4 цифры можно вычислить 32K+ цифр, но делением 32/16 тут уже не обойтись, а если считать по 3 цифры, то можно вычислить в 10 раз больше. Ну а для современных компов можно сделать сумму 64 разряда, умножение 32x32->64 у них есть, в массиве хранить по 9 цифр, и считать вообще до скончания вечности.
А работает алгоритм просто, оригинальный использует два линейных массива: сумма и перенос, если мы к ним добавим еще одну размерность, и результаты каждой итерации будем складывать в свою строку, то окажется, что элемент ячейки зависит только от суммы выше и переноса справа, то есть можно поменять циклы местами, вычислить сначала последний столбец, затем предпоследний и так далее. Сумму между столбцами нам передавать вообще не нужно, поэтому остаётся только столбец с переносами, а от второго массива одна ячейка для хранения суммы во внутреннем цикле.

[ivagor]

Наверно стоит еще уменьшить N, чтобы выдавал только верные цифры, например до N=4935u или N=M/2*1000u/3322u

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

Нетребовательность алгоритма к памяти впечатляет.

[CodeMaster]

100 знаков нам пока за глаза достаточно для начала опытов и поиска решения позволяющего перешагнуть за 1 сек для 100 знаков числа Пи на КР580ВМ80А при его штатных частотах (без разгона).

Что-то мне подсказывает (глядя на алгоритм blackmirror, что получившееся решение ни на что, кроме вычисления Пи (хоть и очень быстро)) будет неспособно. А мне как-то казалось (по ходу темы), что появилась идея найти некие универсальные вычислительные алгоритмы для 8-битных процов. Или я упустил нить повествования и цель просто узнать во сколь раз можно оптимизировать конкретный расчёт между "в лоб" и "через ж..."?