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

[perestoronin]

crc-16 или, если очень хочется, crc-32

Нет не крутовато, если хочется надежности, то даже md5sum слабо, то чего уж говорить про более примитивные.
Кстати а чего крутого в этих простых функциях ? Что испугало ?

[Advertiser]

[ivagor]

чего крутого в этих простых функциях ?

Про крутость я не писал, я писал про достаточность.

[perestoronin]

про достаточность

Даже md5sum не достаточно надежная, от неё все прогрессивное человечество не так давно (что такое 5 лет в нашу эпоху) отказалось в пользу как минимум sha256sum.

В файлах distinfo, использующихся в системе портов FreeBSD для контроля целостности исходных текстов, произошел полный переход на использование алгоритма вычисления контрольных сумм SHA-256. Это означает, что в файлах distinfo от новых пакетов MD5-суммы указываться не будут, а существующие строки с указанием MD5-сумм игнорируются.

Такое решение принято, поскольку алгоритм SHA-256 является более стойким к криптоанализу, чем MD5, а проверка сразу двух видов контрольных сумм не увеличивала бы безопасность.

Хотя мне вариант с контрольной суммой не особо нравится.

Не нравится контрольной суммой, можно по старинке, хранить в листинге 100 верных чисел числа Пи и сравнивать в коде их с тем, что посчитал алгоритм. Тоже вариант
А можно еще, just for fun, вывести двоичное представление числа Пи в прямоугольную область в правом верхнем углу экрана, и рядом ниже выводить посчитанное по тестируемому алгоритму, глаз обычно у всех алмаз, сразу увидит где пиксели различаются.

[ivagor]

Не смог психологически использовать для умножения на 10000 32 килобайта в таблицах как делают некоторые. Использовал таблицу на 768 байт

Временно вернул умножение на 10000 по маленькой таблице, чтобы проверить сколько это дает - всего 2% с копейками.

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

Чтобы закрыть тему влияния больших таблиц убрал еще и таблицу процедур для умножения младшего байта. Суммарный проигрыш (без большой таблицы *10000 и без таблицы процедур для умножения младшего байта) - примерно четыре с половиной процента, т.е. вклад каждой большой таблицы примерно 2 с небольшим процента.

[blackmirror]

Решил проверить насколько хороша формула с арктангенсами:
Pi/4=44*atan(1/57)+7*atan(1/239)-12*atan(1/682)+24*atan(1/12943)
Если считать в лоб по разложению арктангенса в ряд, то для вычислений требуются только операции деления 24/16 и два буфера - для Pi и очередного слагаемого, можно вычислить 115К десятичных цифр, или в два раза меньше, если деление правильно работает только до 2^15. В элементах ряда присутствуют нечётные числа в качестве делителей, на них делить приходится параллельно со сложением или вычитанием. Перенос в соседний байт возникает в 20% случаев, а в следующий уже только в 0.1% случаев. Общее количество операций деления 24/16 примерено 0.4*N^2 (N - число десятичных цифр), но вычисления в алгоритме двоичные. Для gpigot'а требуется 0.83*N^2 операций деления 32/16 и в два раза больше операций умножения 16x16. В общем в данном виде вычисление Pi наверно будет раз в 10 быстрее, если всё не запороть алгоритмом перевода в десятичный вид. Как оказалось, формула 4*atan(1/5)-atan(1/239) требует немного меньше операций, но без расширения разрядности правильно считать будет только 45К цифр.
machin1.txt

[perestoronin]

Ура, нашему полку прибыло, в теме теперь есть и математики.

В общем в данном виде вычисление Pi наверно будет раз в 10 быстрее

Неужели получим вычисление первых 100 цифр числа Пи меньше чем за доли секунды на КР580ВМ80А ?

правильно считать будет только 45К цифр.

А нам то надо всего 0.1К цифр.

[blackmirror]

Неужели получим вычисление первых 100 цифр числа Пи меньше чем за доли секунды на КР580ВМ80А ?

Боюсь, что это будет львиная доля, а то и не одна. Поскольку с вычитанием у него не очень, то для деления придётся занимать все регистры, значит будет развёрнутая процедура, которая загрузит байт, вызовет функцию деления 24/16, сохранит результат. Скорее всего адресацию придётся использовать абсолютную. Еще нужны будут похожие процедуры, которые результат не сохраняют, а вычитают или добавляют к числу Pi, и в некоторых случаях корректируют несколько байт для распространения переноса. Для вывода проще всего 50 раз домножить на 100 при помощи маленькой таблички. Только по мере домножения нужно будет укорачивать обрабатываемую часть, чтобы не обрабатывать мусор в младших разрядах. А при делении наоборот, отбрасывать старшие нули, делить их конечно можно, но зачем?

[ivagor]

Вот этот вариант при замене типов на short правильно считает 4138 цифр. Причем большинство шортов можно заменить на беззнаковые, в т.ч. умножение и деление. Т.е. для расчета 100 и 1000 цифр там достаточно 16*16 и 16/16.

[litwr]

Перенес суперделение на 6502. Трудно догадаться убрать верчение лишнего байта - благодарности уважаемому ivagor'у. Вот код для истории

div16            ;dividend+2 < divisor, CY = 0, AC = dividend+3
.repeat 8
	rol dividend+1
       	rol dividend+2
	rol	
	cmp divisor+1
        bcc l1
        bne l2

        ldx dividend+2
        cpx divisor
        bcc l1

l2      tax
        lda dividend+2
        sbc divisor
        sta dividend+2
        txa
        sbc divisor+1
l1
.endr
        rol dividend+1

.repeat 8
        rol dividend
       	rol dividend+2
	rol	
	cmp divisor+1
        bcc l1
        bne l2

        ldx dividend+2
        cpx divisor
        bcc l1

l2      tax
        lda dividend+2
        sbc divisor
        sta dividend+2
        txa
        sbc divisor+1
l1
.endr
        rol dividend
        sta remainder+1
        lda dividend+2
        sta remainder
        lda #0
        sta dividend+2
	sta dividend+3
	rts

Примерно 460 тактов, для z80 - 840. Итог по скорости 6502 быстрее только менее 90%. В некоторых случаях z80 показывает очень хорошую эффективность. Но на z80 легко писать очень плохие коды, а очень хорошие очень тяжело. С 6502 гораздо легче и коды легко масштабировать, типа сделать 64/32-деление.

Последние данные по программам - дал им версию 1.

Коммодор +4 1.62 - 152.3 - 1362
Амстрад 6128 2.41 - 179.3 - 1582

Как обычно для 100, 1000 и 3000 цифр. Версия для Коммодора считает до 7680 цифр, а для Амстрада до 5536 в бейсике. Кроме того есть сырая версия для Амстрада в СР/М, которая досчитала до 8500 цифр, но может и немного побольше.

Чтобы совсем не пишнуться решил покинуть эту приятную тему. Может через месяц посмотрю, что тут случилось. Может появятся и результаты по БК, Спектрумам или даже лучшему домашнему ПК СССР Поиску? Успехов всем в пи-строительстве!

Какой сильный перекос для 100 и 1000 цифр. То ли умножение на 10000 сказывается, то ли вывод на экран, но ПК-6128Ц и вектор с z80 считают 100 цифр быстрее, а 1000 медленнее.

Конечно, вывод на экран. Под СР/М он ещё раз в 10 (!) медленнее. Зато там можно перенаправить вывод в файл как в ДОСе или Юниксе.
Если хотите сами проверить, то скачайте эмулятор, подсоедините диск и командой RUN"PI проверяйте. Выход в СР/М командой |CPM, но нужен системный диск.
Для Коммодора нужны две команды DLOAD"PI* и RUN

Посчитать можно, а как их контролировать? На экран вектора в 512x256 одновременно можно вывести 5376 символов 4x6 (надо еще написать процедуру вывода). Выводить с прокруткой, сохранять на диск?

По последним цифрам. Алгоритм таков, что сбой накапливается. Для больших чисел можно и на диск сбрасывать. Дело автора.

А можно еще, just for fun, вывести двоичное представление числа Пи в прямоугольную область в правом верхнем углу экрана, и рядом ниже выводить посчитанное по тестируемому алгоритму, глаз обычно у всех алмаз, сразу увидит где пиксели различаются.

Круто! Но в некоторых системах есть текстовые режимы...

[perestoronin]

Но в некоторых системах есть текстовые режимы

Для таких случаев вполне сгодится сравнение sha256sum с эталоном.

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

Вот код для истории

Листинг бы продублировать и в виде вложения. Для удобства.