ass (шутники) по картинке понравился, но увы есть отличия в синтаксисе от tasm и справка в 7ке не смотрится.
Этот файл есть в архивеЦитата:
Сообщение от perestoronin
Вид для печати
ass (шутники) по картинке понравился, но увы есть отличия в синтаксисе от tasm и справка в 7ке не смотрится.
Этот файл есть в архивеЦитата:
Сообщение от perestoronin
Благодарю, все еще в поиске исходника tasm или хотя бы linux версии, на данный момент нашел вот такой архив, в нем есть документация в pdf по программированию для процессора 6502, думаю может быть полезна для тех, кто разрабатывает версию программы расчета числа Пи под процессор 6502 (NES, Агаты, Анюша, Apple 1).Цитата:
Сообщение от ivagor
Левенталь 6502 Подпрограммы на ассемблере (книга на английском).
в том же архиве находится и сам tasm 3.2, но с таблицей только для 6502.
Подумалось, что наверное не так сложно будет мне расковырять tasm с целью получить fork в исходниках, а сами таблички-то просто текстовые файлы, их можно использовать будет без изменений в авторской редакции.
tasm мега компилятор с ассемблера, и сразу под массу процессоров, среди которых есть почти все нужные нам ретро-процессоры.
Не представляется сложным написать самим таблички под какие-то другие более экзотичные процессоры :), для этого и программирование даже знать и не нужно :)
Не особенно тщательно искал но на той же страничке проекта много чего выложено, может еще что-то найдется в тех архивах уникальное, как к примеру выше упомянутая версия книги Левенталя для 6502, дайте знать и мне.
Ждем теперь оптимизированную версию расчета чиста Пи по неоптимальному алгоритму и для процессора 6502 ;)
Как вижу, деление работает с любым делителем до 2^16, это действительно необходимо? Уменьшение диапазона в два раза позволит выкинуть половину кода, а из оставшейся половину условных переходов. Вроде бы алгоритму "краника" деления на числа до 2^15 хватает для вычисления 4930 десятичных знаков.Цитата:
Сообщение от ivagor
Судя по времени работы текущая версия litwr весьма оптимизирована:Цитата:
Сообщение от perestoronin
Цитата:
Сообщение от litwr
Это большой плюс tasma, который перевешивает (для меня) его недостатки.Цитата:
Сообщение от perestoronin
- - - Добавлено - - -
Да, старший бит делителя бывает единичным. Диапазоны чисел я проверял, в умножении учет диапазона хорошо помог, а в делении, к сожалению, нет.Цитата:
Сообщение от blackmirror
? Не могу сообразить, за счет чего можно выкинуть половину кода при уменьшении диапазона в два раза. На каждый бит делимого приходится 8 строк.Цитата:
Сообщение от blackmirror
- - - Добавлено - - -
Это Вы наверно про исходный, а здесь то "4х циферный"Цитата:
Сообщение от blackmirror
весьма вероятно что это так, но цифры уж очень близки к версии для 8080, поэтому думаю что это именно весьма неоптимизированная версия, при равной частоте с 8080, должна получаться версия быстрее для 6502.Цитата:
Сообщение от ivagor
память можно рассматривать и как массив байт и как массив бит, другое дело что обращение к памяти как к массиву бит потребует накладных расходов, тут нужно внимательно смотреть сколько выигрываем и сколько проиграем в производительности и объеме памяти.Цитата:
Сообщение от ivagor
В дополнение старый список инструментов для компиляции программ под ретропроцессоры
http://www.z80.info/z80sdt.htm
увы ни исходника tasm, ни версию для linux, я не нашел, но зато нашел другой ассемблер и тоже управляемый таблицами и причем с исходными кодами самого ассемблера:Цитата:
Сообщение от perestoronin
http://www.penguin.cz/~niki/tdasm/
думаю будет полезен и для Z80, тем более что таблица (хотя и неполная) для z80 прилагается, а полные таблицы и отсутствующие таблички можно попробовать портировать для tdasm из архива tasm, но форматы таблиц различны.
PS. В целом мне кажется tdasm не дотягивает до уровня tasm, поэтому ищу исходники или версию tasm под linux дальше.
еще наткнулся на vasm, тоже достоен внимания http://sun.hasenbraten.de/vasm/index.php?view=relsrc
Мой код начинает работать с R<B, и на каждом шаге остаток удваивается с добавлением очередного бита делимого, после чего к нему либо прибавляется либо вычитается B, чтобы |R| оставался меньше B, а далее можно обрабатывать следующий бит. Если B<2^15, то |R|<2^15 на каждом шаге, и после удвоения переполнения произойти не может, а условный переход требуется только чтобы отследить момент, когда сложение с B нужно заменить вычитанием. А вот если |R|>=2^15, то здесь требуется дополнительное ветвление, чтобы правильно отследить знак после добавления/вычитания B.Цитата:
Сообщение от ivagor
В версии для 8080 "удвоенное" количество кода вызвано отсутствием команды HL=HL+RP+флаг переноса. В вариантах для 8085 и z80 код почти как у Вас, только с переходами по переносу, а не знаку.
- - - Добавлено - - -
Поправлюсь - на каждый бит делимогоЦитата:
Сообщение от ivagor
- - - Добавлено - - -
Уф, это я опять про делимое, а не про делитель. Максимальный делитель для 1000 - 6999, для 100 - 699. Не думаю, что это можно использовать для сокращения процедуры при расчете 1000 или 100 цифр. Вот если бы делимое, которое я как раз имел в виду, тогда другое дело.Цитата:
Сообщение от ivagor
Я скачивал с официальной странички, сейчас уже не открывается, но есть в веб-архиве.Цитата:
Сообщение от perestoronin
а другие на ретро-железках еще и деньги зарабатывают, с каждой копии своей программы по 100 сантиков:Цитата:
Сообщение от b2m
http://www.cdadapter.com/cross32.htm
Вот нам и Licensing Best Practices в действии.
8080 гадость конечно редкостная, но даже для него с делением не всё так плохо:Цитата:
Сообщение от ivagor
Цитата:
#define ADC8(a,b) do{a=(a&255)+(b&255)+C; C=a>>8; a&=255;}while(0)
#define ADD16(a,b) do{a=(a&65535)+(b&65535); C=a>>16; a&=65535;}while(0)
//BC - делитель, должен быть в диапазоне от 256 до 32768
//DE = -BC
//HL < BC - старшие два байта делимого
//SP - младший байт делимого расширенный нулём
//A - частное
//деление производится по формуле A=HL*256/BC; HL=HL*256%BC; HL+=SP; if(HL>=BC) {HL-=BC; ++A;}
void div_8080(int &hl, int &a, int &bc){
int sp=a;
int de=-bc;
int C=0;
ADD16(hl,hl); ADD16(hl,de); if(!C) goto A1;
S1: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A2;
S2: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A3;
S3: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A4;
S4: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A5;
S5: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A6;
S6: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A7;
S7: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A8;
S8: ADC8(a,a); ADD16(hl,sp); ADD16(hl,de); if(!C) goto A9;
S9: ADC8(a,0);
return;
A1: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S2;
A2: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S3;
A3: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S4;
A4: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S5;
A5: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S6;
A6: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S7;
A7: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S8;
A8: ADC8(a,a); ADD16(hl,sp); if(C) goto S9;
A9: ADD16(hl,bc);
return;
}
Народ на лимонном форуме протестировали версию для Коммодора 64 с разными 8085 и 580ВМ1 :) или, точнее, с Хамелеоном и Суперпроцесором (SuperCPU довольно массовая приставка для означенного Коммодора, эмулируется в Vice). Результаты от 16 до 22 раз быстрее Коммодора 64. Это даже Вектору с Турбо+ многовато. Там ещё обозначилась тема не вполне точной эмуляции ускоряющих приставок.
Кстати, для интересующихся z80 самый быстрый относительно массовый компьютер на его основе - это SAM Coupé с z80 на 6 MHz, выпускавшийся с 1989 (!). Хотя сэр Синклер вроде собирался новый Спектрум сделать на 8 МГц, но "переспешил" на "квантовом скачке" с QL и сдал хозяйство консервативному Амстраду. Амстрад в 1992 сделал что-то на z80 c 16 Мгц, но в единичных экземплярах.
blackmirror, интересный вариант, но 100 цифр с ним считается медленнее, а 1000 с той же скоростью, как здесь. Это без sp, с ним еще медленнее, плюс сложность с подсчетом времени. Возможно моя реализация была недостаточно эффективна и кто-нибудь сильнее раскроет потенциал этого варианта.
Тогда я бы сравнил реализации на ПЛИС, думаю 6502 будет быстрее максимум раза в 2.Цитата:
Сообщение от litwr
- - - Добавлено - - -
Если уж сравнивать с 65816, то и на стороне z80 пусть играет r800 в MSX Turbo R.Цитата:
Сообщение от litwr
- - - Добавлено - - -
Маленько оптимизировал, теперь 100 считаются с той же скоростью, а 1000 цифр на 5 секунд быстрее - неплохо.Цитата:
Сообщение от ivagor
- - - Добавлено - - -
Добавил ветку для делителя<128 - 100 цифр стало быстрее на 0.06 сек, 1000 цифр - еще на 0.6 секунды (т.е. в сумме по сравнению с выложенной версией почти на 6 сек).
ivagor, вообще можно не тащить младший байт в процедуру деления, а добавить его уже после выхода, грузить можно самомодифицируемыми командами LXI, потому что после умножения наверно не сильно принципиально, куда сохранять два младших байта, ну а чтобы проще было проверить, не нужно ли после сложения править частное/остаток, процедуру деления можно чуть изменить, чтобы она работала с отрицательными остатками.
Цитата:
#define ADC8(a,b) do{a=(a&255)+(b&255)+C; C=a>>8; a&=255;}while(0)
#define ADD16(a,b) do{a=(a&65535)+(b&65535); C=a>>16; a&=65535;}while(0)
//вход:
//BC - делитель, должен быть в диапазоне от 256 до 32768
//DE = -BC
//HL - два байта делимого минус BC, |HL+BC|<BC
//выход:
//A - HL*256/BC
//HL - HL*256%BC-BC
void div_8080(int &a,int &bc, int &de,int &hl){
int C=0;
ADD16(hl,hl); ADD16(hl,bc); if(C) goto S1;
A1: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S2;
A2: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S3;
A3: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S4;
A4: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S5;
A5: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S6;
A6: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S7;
A7: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S8;
A8: ADC8(a,a);
return;
S1: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A2;
S2: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A3;
S3: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A4;
S4: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A5;
S5: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A6;
S6: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A7;
S7: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A8;
S8: ADC8(a,a); ADD16(hl,de);
return;
}
//bb делитель от 256 до 32768
//aa - делимое, aa<65536*bb
void div_32_16(int aa, int bb){
int a,bc,de,hl,C;
hl=aa>>16;//старшие два байта делимого
bc=bb;//делитель
de=-bb&0xFFFF;//-делитель
ADD16(hl,de);//корректируем старшие два байта, потому что деление работает с отрицательным остатком
div_8080(a,bc,de,hl);//делим 256*HL на BC
//PUSH BC
bc=(aa>>8)&255; //перед делением модифицируем данную команду LXI, чтобы загрузить предпоследний байт делимого
ADD16(hl,bc); //суммируем предпоследний байт делимого с остатком
bc=bb;//POP BC
if(C){//если остаток стал положительным, то корректируем остаток и старший байт частного
ADD16(hl,de);
++a;
}
printf("%3X",a);//старший байт частного
div_8080(a,bc,de,hl);//делим дальше
de=aa&255;//перед делением модифицируем данную команду LXI, чтобы загрузить младший байт делимого
ADD16(hl,de);//суммируем младший байт делимого с остатком
if(C)//если стал положительным, то корректируем младший байт частного, иначе корректируем остаток
++a;
else
ADD16(hl,bc);
printf("%02X",a);
printf("%4X",hl);
}
Я так и сделал. Но я сейчас складываю внутри, на "после" может потом переделаю. Сейчас тяжеловесно выглядит ветка для 127<делителя<256, может для нее что-нибудь придумаю.Цитата:
Сообщение от blackmirror
Там похоже без удвоения разрядности никак, то есть в BC придётся грузить делитель*128, начинать не с удвоения HL, а с вычитания, ну а в конец добавить удвоение HL, чтобы весь остаток оказался в H, в A мы получим байт частного, а в L нужно загрузить следующий байт делимого.Цитата:
Сообщение от ivagor
Вы и это в Вектор вставите? :):):)Цитата:
Сообщение от ivagor
Кстати, Хамелеон это именно ПЛИС и возможно лучший из существующих эмулятор такого рода - рекомендую посмотреть, позавидовать. :)
Перенёс final_precise на СР/М на Амстраде (Вложение 55411) и результаты получились странные: 100 цифр за 2.81 (2.98 - ваши данные), 1000 цифр за 253.9 (299) - это на 100 цифрах получается Амстрад быстрее на тех же кодах только на 6%, что делает эффективную частоту Bектора чуть-чуть большей 3 МГц... Хотя возможно нашёл объяснение: торможение BDOS - вы вместо него используете что-то побыстрее. Без печати Амстрад делает 100 цифр за 2.49, а 1000 за 250. С такими таймингами Амстрад стабильно на 19% быстрее по 100 и 1000 цифрам, что тактирует Вектор в 2.68 МГц!
Получается, что на 100 цифрах на 15% сравнивается скорость печати символов на экран. С ростом скорости основного алгоритма эта доля будет расти... Уже писал об этом - кажется, что такая оптимизация не есть что-то правильное... Интересно бы данные по Корвету получить, Микроше и т.п.
Раньше время измерялось из бейсика и поэтому в данных по Амстраду учитывалось и время построения таблиц, но это примерно полсекунды в final_precise, влияет только на результаты по 100 цифрам. И повторю вопрос. Почему не класть таблицы готовыми? При загрузке система сразу определит хватает ли ей памяти... И тестировать проще и вам меньше кода носить.
A коды интересные: штучки вроде check - это даже слов не нахожу - прямо пимания какая-то. :)
Вполне возможно, что тормозит вывод на экран. В векторовских cp/mах эта проблема есть, поэтому я и сделал стэндэлон.Цитата:
Сообщение от litwr
Просто лень.Цитата:
Сообщение от litwr
Как видите проблема есть не только у Вектора. Без такого, что вы сделали с кодом, мы могли бы сравнивать разные системы. Например, Корвет мог бы быть быстрее на 100 цифрах, но медленнее на 1000. Это бы реально отражало архитектурные особенности компьютеров, а не трудовое усердие энтузиастов.Цитата:
Сообщение от ivagor
Уважаемый perestoronin, на лимонном форуме (http://www.lemon64.com/forum/viewtop...r=asc&start=24) выложены данные по железному самому быстрому Коммодору в сравнении с программой на си.
Предлагаю ограничиться, пока не пройдем барьер 1сек, для КР580ВМ80А на его штатных частотах, 100 цифрами, а 1000 приводим справочно, по желанию, и лишь для тех архитектур и алгоритмов, которые уже преодолели 1 с. Для остальных случаев остановимся на глубокой оптимизации для лишь для 100 цифр.Цитата:
Сообщение от litwr
То, что прислушались к совету вынести вывод результата в отдельный код, отдельно от кода расчета, благодарствую и приветствую, так значительно легче сравнивать и искать причину деградации скорости расчета в сравнении с предыдущими предложенными вариантами.
Это не интересно, Си заведомо в невыгодной позиции, думаю это должно быть уже давно очевидно быть. На Си быстрее кодить в продакшн, когда работа должна быть завершена еще вчера, но создавать шедевры, доступные лишь свободному художнику, на Си сложнее, чем на ассемблере, если вообще возможен шедевр на Си. Я знаю лишь один пример шедевра на Си - веб-сервер nginx, остальное всё - изделия для "продакшн", пускай даже и с лейблой СПО.Цитата:
Сообщение от litwr
Кто бы потрудился из знатоков Коммодоров и еже с ними Хамелеонов, смог проинтерпретировать те расчеты? А также привести подробности того самого расхваливаемого Хамелеона, разрядность этого сопроцессорного блока на ПЛИС (если я правильно понял) и его тактовую частоту.Цитата:
Сообщение от litwr
Можно краткую выжимку сюда запостить, как ранее делали, 100 знаков (на такой то машине столько-то 0,00хх сек, с ускорителем Хамелеон столько то ..., Хамелеон разрядность хх бит, частота хх МГц, команды умножения такие-то, столько-то тактов) ?
Конечно любопытно знать, что кроме 1801ВМ1 и 580ВМ80 что-то еще существует, но нам бы в первую очередь доступное железо прогнуть нужно ;)
Хотя думаю в Евросоюзах наверное Коммодоры достаются за "500р", а то и вовсе за 10 рублей как в России в Митино процессоры КР580ВМ80А ? Впрочем можно и к ретро-машине соорудить приставочку на ПЛИС и на мощном ARM-процессоре и похвалиться какие мы молодцы, только зачем ? Пока в этом не вижу необходимости, есть запас и без сопроцессоров для достижения новых рекордов, до 1 сек "еще далеко".
Также не понятно зачем в той теме прикрывают расчёт чисел числа Пи заголовком "демо", вместо нормального названия. Чего стесняются ?
Мое мнение насчет разделения расчета и вывода на экран - это нормально только для расчета 100 цифр. Несколько секунд можно и подождать, когда казалось бы ничего не происходит. А для 1000 цифр это уже не здорово. Насколько помню, litwr писал нечто похожее, т.е. я фактически присоединяюсь к его мнению по этому вопросу.
Можно сделать версию для cp/m, но не знаю универсального способа подсчета времени, разве что поручить это "оператору" с секундомером.
Насчет быстродействия реализаций на ПЛИС - v06cc svofski в максимальном разгоне, который мне удался на DE1, работал примерно в 12 раз быстрее стандартного вектора. Для DE1-SoC и DE2-115 можно сделать и побыстрее, да и для DE1 предел не достигнут, но оказалось, что на векторе практически нет программ, которым нужно такое быстродействие.
Мелко как-то, даже Командор 64 с текущим алгоритмом почти 5000 знаков может считать. Это машина класса Вектора.Цитата:
Сообщение от perestoronin
Что-то вы странное про си написали. На нём библиотеки пишут для всяких питонов и сами питоны. На ассемблере тольку управление памятью и ввод-вывод с железом.
Данные для SuperCPU - довольно массовой (10-и тысяч) приставки из 90-х. А Хамелеон это продолжение разработки уже почти легендарной компьютерной девушки Джерри - это уже 21 век, разработка продолжается. Можно воткнуть в C64, а можно в него воткнуть usb-клавиатуру.- https://icomp.de/shop-icomp/en/produ...meleon_64.html
Таким мнением вы внесли в тему политику, поиск преференций для выбранной платформы. :(Цитата:
Сообщение от ivagor
Уже выложил такую для final-precise. А универсального способа работы с таймером в ср/м нет, нужно подстраиваться под каждый случай. В выложенной версии используются обращения к фирменным ROM-вызовам.Цитата:
Сообщение от ivagor
Непротрезвел что-ли? Какая тут политика? Совсем обалдели...Цитата:
Сообщение от litwr
До 10го мало кто из коллег будет трезвым (я не в счет, т.к. "его" не пью), не пьют лишь только убежденные трезвенники и язвенники. Но среди непьющих % в последние годы выше тех, кто не пьёт по убеждению и это не может не радовать меня.Цитата:
Сообщение от b2m
А на счет преференций, так оно так все и делается, нужно продвигать отечественную продукцию, а её в Митино очень много :) и не дороже чем по 30 руб за микросхему КР580ВМ80А.
Зачем нам Коммодоры и Эпплы 1, когда у нас и КР580ВМ80А не до конца прокачан :) ? Не у всех есть лишние ресурсы по времени чтобы заниматься сразу несколькими архитектурами, да и не всем оно по большому счету нужно. Но это не значит что нам не интересно что творится в плане войны с числом Пи у них там, интересны сводки с фронта Коммодора и Эппла, но желательно не отсыл на сайты с ихними кракозябрами, которые даже гуглопереводчик не может правильно и понятно перевести, а выжимки сюда в тему с циферками на русском языке, для простоты можно присылать краткое описание новизны алгоритмов и достигнутые улучшения подкрепленные полученными сек за 100 знаков.
100 знаков нам пока за глаза достаточно для начала опытов и поиска решения позволяющего перешагнуть за 1 сек для 100 знаков числа Пи на КР580ВМ80А при его штатных частотах (без разгона).
Вложение 55419Вложение 55420
100 - 2.7568 сек
1000 - 280.9320 сек - 4 мин 40.9320 сек
А Phenom то может посчитать сколько циферок! Главное чтобы места на жестком диске в 4Тбайта для результата было :)Цитата:
Сообщение от litwr
А теперь вернемся к нашим баранам, т.е. к 100 циферкам и удобному, для поиска слабых мест в примитивных алгоритмах, процессору КР580ВМ80А, коих полно у каждого, не то, что экзотичные в наших краях иностранцы, интересно коим боком их заносит под Москву ? Ну не каждому дано владеть разными машинками Тюринга и Поста.
Технарям попроще ставить эксперименты именно на простых процессорах - типа проверенных временем и к тому же по прежнему доступных КР580ВМ80А и КР1858ВМ*.
Но за циферки все равно спасибо, впрочем и за Си с Бейсиками тоже. Вот еще бы кто на Форте поупражнялся в скорости расчета числа Пи ;)
Если spigot'а перевернуть, то есть внутренним циклом проходить по переносам(от старших к младшим), а внешним по множителям/делителям(в убывающем направлении), то понадобится только массив переносов. При вычислении по 4 цифры переносы будут меньше 10000*2, и хранить потребуется 1000/4*2=500 байт. На каждой итерации внешнего цикла можно сгенерировать оптимальный код для внутреннего, поскольку там требуется только умножение/деление на константу. Вычислений здесь меньше конечно не станет, но не понадобится делать CALL/RET, насиловать стек, да и искать процедуру по таблице. После завершения внешнего цикла, нужно еще раз пройтись по переносам, приводя их к диапазону до 10000, и увеличивая соседний если нужно. Никаких "недействительных" цифр здесь не будет, если двигаться от младших к старшим. Если сделать процедуры умножения/деления 16x24->40, 40/24->16_24, то можно будет вычислять хоть 100К цифр, сейчас это конечно смысла не имеет, но 20 лет назад вычислить 100К цифр при 64К памяти было бы неплохо, пусть даже и за несколько месяцев.
Вложение 55424
Сумма вычисляется по формуле s=s*10000+p[i]*a, затем это делится на b. Поскольку a и b во внутреннем цикле можно считать константами, то возможно получится одновременно умножать на 10000 и делить на b, не вылезая за пределы 16 бит. По крайнем мере в той ветви алгоритма где делитель прибавляется, можно сначала добавить множитель, и если результат станет положительным, значит на данном шаге делитель нужно вычитать. Оптимизация здесь возможна за счёт того, что сдвиг суммы станет общим для умножения и деления, и вроде как не потребуется подгружать младшие байты для следующих итераций. А вот про p[i] можно сразу сказать, что частное будет равно 0, поскольку a<b, и вычислять нужно только остаток. Но эти идеи еще нуждаются в проверке.
Интересный подход. Если честно - я не осмыслил, как это работает, но попробовал. Выложенный вариант начиная с 4934 цифры считает неправильно (последние правильные цифры - 3096, потом д.б. 3408).
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 цифр, и считать вообще до скончания вечности.
А работает алгоритм просто, оригинальный использует два линейных массива: сумма и перенос, если мы к ним добавим еще одну размерность, и результаты каждой итерации будем складывать в свою строку, то окажется, что элемент ячейки зависит только от суммы выше и переноса справа, то есть можно поменять циклы местами, вычислить сначала последний столбец, затем предпоследний и так далее. Сумму между столбцами нам передавать вообще не нужно, поэтому остаётся только столбец с переносами, а от второго массива одна ячейка для хранения суммы во внутреннем цикле.
Наверно стоит еще уменьшить N, чтобы выдавал только верные цифры, например до N=4935u или N=M/2*1000u/3322u
- - - Добавлено - - -
Нетребовательность алгоритма к памяти впечатляет.
Что-то мне подсказывает (глядя на алгоритм blackmirror, что получившееся решение ни на что, кроме вычисления Пи (хоть и очень быстро)) будет неспособно. А мне как-то казалось (по ходу темы), что появилась идея найти некие универсальные вычислительные алгоритмы для 8-битных процов. Или я упустил нить повествования и цель просто узнать во сколь раз можно оптимизировать конкретный расчёт между "в лоб" и "через ж..."?Цитата:
Сообщение от perestoronin
? Насколько могу судить, реализованные алгоритмы умножения и, особенно, деления (blackmirror) для 8080 самые быстрые. А деление так и для z80 самое быстрое, или есть быстрее? Для универсальности нужно кое-что добавить, но это не принципиально.
- - - Добавлено - - -
Пару слов о широте охвата процессоров. Я лично за максимальный охват, массовые и экзотические, простые и сложные - чем больше тем лучше. Могу только повторить респект litwrу за многопроцессорность.
Парни, так для Спектрума (Z80) есть готовый исполняемый супер-пупер-оптимизированный бинарник с запросом "сколько цифр считать" и подсчётом времени выполнения?
Цитата:
Сообщение от CodeMaster
Универсальные не требуются, т.к. скорости от них, как после написания программы на Си и её первичной оптимизации руками после перевода на ассемблер.Цитата:
Сообщение от ivagor
Что делать с примерами "чрезмерно" оптимизированными к примеру на КР580ВМ80А, это уже решать тем, кому этот пример достанется.
Самое лучшее что можно рекомендовать, это сопроводить грамотными краткими комментариями свои шедевры.
А универсальные в нашем случае не дадут максимальной скорости.
Все что сейчас требуется, используя найденные самые быстрые реализации умножения и деления для КР580ВМ80А (впрочем и КР1858ВМ* /Z80) в частности), подобрать самые быстрые алгоритмы собственно расчета 100 цифр числа Пи.
Аналогичное после можно будет проделать и для остальных процессоров, к примеру для 6502 и КР1801ВМ*.
После чего можно будет констатировать "действительные" скорости и вычислительные возможности этих доступных сейчас в России и Китае ретропроцессоров.
Эти же подходы и алгоритмы позволят оптимизировать и другие, ранее не самые быстрые программки.
Расчет числа Пи самое простое что можно было предложить, и суть расчета чего понятна и гуру и новичку, и результат достигается достаточно быстро и наглядно :) А главное какой прогресс - с минуты до нескольких секунд! И главное, уверен, 3 секунды это еще не предел, при выборе другого алгоритма, при удачном выборе, возможно получить более лучший результат.
Все же первый вариант на ассемблере считал быстрее минутыЦитата:
Сообщение от perestoronin
Не припомню. В шапке темы нет ? Сюда бы Alone, он бы выдал нагора суперПи для Z80 ;)Цитата:
Сообщение от SoftFelix
Но вроде бы его сейчас волнуют больше земные ценности, а не спектрумовские, чуть позже возможно присоединится и тогда будет желаемое здесь.
Особенно интересен результат на 20МГц на Профи, впрочем и на 14МГц для ZX-Evo тоже будет интересен.
Цитата:
14МГц (мега турбо режим с WAIT)
Верное замечание, поправил.Цитата:
Сообщение от ivagor
Дошло, тут тема 8080, а все остальное сбоку. Хотя быстрый вывод на экран проблема частная, неинтересная, присущая и БК, и Спектруму, и Амстраду, ... И поднимать её было немного по моему скромному мнению не совсем прилично. Типа "защитим наши Жигули" от Вольво (Коммодора) и Москвича (Корвета) - 100% политика. А делать можно просто для 1000 и больше знаков и нет проблемы.
Похоже надвигается смена алгоритма. С текущим версия для Амстрада под СР/М может до 8000 знаков считать.
Но пока использовал предложенный уважаемым ivagor супер-алгоритм для деления в версии для Амстрада и получил новые цифры (для 100, 1000, 3000). Для коммодора деления ещё не перенёс, но кое-что улучшил.
Коммодор +4 - 1.72 - 172 - 1545
Амстрад 6128 - 2.48 - 186.5 - 1646.8
В коммодоровской версии использовал разные банки памяти, что позволило считать до почти 8000 цифр, но замедлило на несколько процентов. Не смог психологически использовать для умножения на 10000 32 килобайта в таблицах как делают некоторые. Использовал таблицу на 768 байт - это отнимает у версии Амстрада примерно 30 тактов в каждом цикле.
Удивительно, но Амстрад обогнал Коммодор 128. В некоторых частных случаях (копирование памяти, деление 32/16, ...) z80 показывает отличную эффективность, уступая не более 50% 6502. Хотя с переносом супер-деления 6502 наверное доведет перевес до 70-80%.
БК по-прежнему никто не тестирует. :-( Уважаемый ММ помог не так давно по теме с бейсиком...
Коммодору понадобится всего-то 172*100² с ≈ 20 суток. :)Цитата:
Сообщение от blackmirror
Все БКшники находятся на отдыхе до 10 января :)Цитата:
Сообщение от litwr
результаты обновил в шапкеЦитата:
Сообщение от litwr
Тут тема для всех процессоров, которые доступны, а остальные уже как получится, если есть кому проверить, написать, то и на том благодарствуем владельцам иномарок, только вот не понимаю почему молчат те, кто нажил иномарки в России непосильным трудом :)Цитата:
Сообщение от litwr
Какой сильный перекос для 100 и 1000 цифр. То ли умножение на 10000 сказывается, то ли вывод на экран, но ПК-6128Ц и вектор с z80 считают 100 цифр быстрее, а 1000 медленнее.Цитата:
Сообщение от litwr
Посчитать можно, а как их контролировать? На экран вектора в 512x256 одновременно можно вывести 5376 символов 4x6 (надо еще написать процедуру вывода). Выводить с прокруткой, сохранять на диск?Цитата:
Сообщение от litwr
С учетом увеличения разрядности умножения и деления скорее всего будет дольшеЦитата:
Сообщение от litwr
Много цифр пока рано считать. А контроль можно наладить уже сейчас, например по какой-нибудь быстрой короткой хэш-функции, коих море и которые на выходе выдают для длинного входного массива двоичных данных контрольное относительно короткое число - как результат хэш-функции. Его же заранее обсчитать для 100 цифр результата и сравнивать с результатом аналогичной функции. Кстати в рамках задачи по расчету числа Пи очень полезное упражнение, причем не сложнее чем собственно алгоритмы расчета числа Пи. Эти функции тоже желательно заоптимизировать. Рекомендую начать с устаревшей md5sum и затем продолжить с более надежной sha256sum. Кстати они, как и подпрограммы быстрого деления и умножения длинных чисел (десятки и сотни цифр в числе), будут очень полезны не только как наглядное пособие для изучающих программирование на ретропроцессорах.Цитата:
Сообщение от ivagor
Заниматься же оптимизацией вывода результата на экран тоже нужно, но эту задачку, относительно простую, лучше отложить, сделав предположение что вывод уже давно заоптимизирован дальше не куда :) Тем более мы договорились время вывода из памяти результат расчета на экран исключить из рейтинга алгоритмов расчета.
Отправными точками можно считать следующие реализации на ассемблере алгоритмов упомянутых хэш-функций для оффтопика :)
http://www.nayuki.io/res/fast-sha2-h...embly/sha256.S
http://www.nayuki.io/page/fast-sha2-...n-x86-assembly
http://www.nayuki.io/res/fast-md5-ha...bly/md5-fast.S
http://www.nayuki.io/page/fast-md5-h...n-x86-assembly
md5, sha256 - не крутовато ли для данного применения? ИМХО вполне хватит crc-16 или, если очень хочется, crc-32. Хотя мне вариант с контрольной суммой не особо нравится.