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

[perestoronin]

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

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

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

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

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

[Advertiser]

[ivagor]

С 6502 гораздо легче и коды легко масштабировать, типа сделать 64/32-деление

Выкладывал тут версию легко масштабируемого деления для 8080, практически в стиле 6502, все в памяти. Но очень медленно.

[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.

[blackmirror]

Формула 12*atan(1/18)+8*atan(1/57)-5*(atan(/239), по сравнению с 4*atan(1/5)-atan(1/239) требует на пару процентов меньше делений, но в последней формуле, применительно к вычислению 100 знаков, делить на 239^2 требуется только в 11% случаев, во всех остальных - делить нужно на числа менее 256, то есть для i8080 самый оптимальный вариант. С 8 разрядным делением всё просто, в HL делимое, в BC делитель*128, DE=-BC, ну а дальше сначала складываем(вычитаем), делаем если нужно переход, добавляем разряд частного к A, потом удваиваем HL. Ну а в 16-разрядном сначала удвоение HL, переход по переполнению, сложение(вычитание), переход, в половине ветвей добавление разряда частного к A(можно сразу добавлять 2^n, ничего не сдвигая). На выходе должен получиться отрицательный остаток, чтобы к нему можно было добавить байт и сразу скорректировать остаток/частное, если было переполнение. В общем по сравнению с 8-разрядным делением, требующим 4 команды на бит, здесь потребуется дополнительный переход, и несколько команд в конце для добавления байта.

В качестве обобщения, прицеплю сюда небольшую модификацию беззнакового деления с 4 ветвями, можно выкинуть половину и чуть ускорить, если делителей более 2^15 не требуются, а для Z80 можно легко расширить до 32х разрядного делителя, если делать обмен регистров. udiv16.txt

Еще наткнулся в википедии на Метод БВЕ, смысл которого в том, что слагаемые группируются сначала парами, общий множитель выносится за скобки, а оставшиеся дроби приводятся к общему знаменателю и складываются, далее пары опять объединяются и таким же образом вычисляются новые дроби. А в конце нужно будет просто поделить два очень больших числа. Можно даже на завершающих шагах не вычислять больше требуемой точности, но плавающая точка с мантиссой переменной длины это наверно будет жесть и для 100 или 1000 цифр эффекта не даст.

[litwr]

Что-то тут всё стихло. Немного пооптимизировал версию для 8086.
По IBM PC 5150 - 40.4 c на 1000 знаков,
по IBM PC 5170 (AT 6 MHz) - 8.2 cек на 1000 знаков. АТ в 5 раз почти быстрее на пи, чем ХТ. Использовал эмулятор с http://pcem-emulator.co.uk/
Кажется, что он чуть быстрее, чем следует.

[LeoN65816]

Аналогичный бенчмаркнайзер на асме 65816 - "Решето Эратосфена".

[perestoronin]

Для предварительной оценки сложности вычислений можно использовать встроенный в любой linux калькулятор командной строки, к примеру как расписано здесь

$ { echo -n "scale=100;"; seq 1 2 200 | xargs -n1 -I{} echo '(16*(1/5)^{}/{}-4*(1/239)^{}/{})';} | paste -sd-+ | bc -l
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679

возможно сработает и такой там же предложенный способ, но только вот верные ли цифры я не проверял:

# echo "scale=1000; 4*a(1)" | bc -l
3.141592653589793238462643383279502884197169399375105820974944592307\
81640628620899862803482534211706798214808651328230664709384460955058\
22317253594081284811174502841027019385211055596446229489549303819644\
28810975665933446128475648233786783165271201909145648566923460348610\
45432664821339360726024914127372458700660631558817488152092096282925\
40917153643678925903600113305305488204665213841469519415116094330572\
70365759591953092186117381932611793105118548074462379962749567351885\
75272489122793818301194912983367336244065664308602139494639522473719\
07021798609437027705392171762931767523846748184676694051320005681271\
45263560827785771342757789609173637178721468440901224953430146549585\
37105079227968925892354201995611212902196086403441815981362977477130\
99605187072113499999983729780499510597317328160963185950244594553469\
08302642522308253344685035261931188171010003137838752886587533208381\
42061717766914730359825349042875546873115956286388235378759375195778\
18577805321712268066130019278766111959092164201988

1000 знаков этот метод общелкивает менее чем за секунду, а вот 10000 лучше не пробывать так считать - "подвесил" машину на пару минут точно

Скрытый текст

# echo "scale=10000; 4*a(1)" | bc -l
3.141592653589793238462643383279502884197169399375105820974944592307\
81640628620899862803482534211706798214808651328230664709384460955058\
22317253594081284811174502841027019385211055596446229489549303819644\
28810975665933446128475648233786783165271201909145648566923460348610\
45432664821339360726024914127372458700660631558817488152092096282925\
40917153643678925903600113305305488204665213841469519415116094330572\
70365759591953092186117381932611793105118548074462379962749567351885\
75272489122793818301194912983367336244065664308602139494639522473719\
07021798609437027705392171762931767523846748184676694051320005681271\
45263560827785771342757789609173637178721468440901224953430146549585\
37105079227968925892354201995611212902196086403441815981362977477130\
99605187072113499999983729780499510597317328160963185950244594553469\
08302642522308253344685035261931188171010003137838752886587533208381\
42061717766914730359825349042875546873115956286388235378759375195778\
18577805321712268066130019278766111959092164201989380952572010654858\
63278865936153381827968230301952035301852968995773622599413891249721\
77528347913151557485724245415069595082953311686172785588907509838175\
46374649393192550604009277016711390098488240128583616035637076601047\
10181942955596198946767837449448255379774726847104047534646208046684\
25906949129331367702898915210475216205696602405803815019351125338243\
00355876402474964732639141992726042699227967823547816360093417216412\
19924586315030286182974555706749838505494588586926995690927210797509\
30295532116534498720275596023648066549911988183479775356636980742654\
25278625518184175746728909777727938000816470600161452491921732172147\
72350141441973568548161361157352552133475741849468438523323907394143\
33454776241686251898356948556209921922218427255025425688767179049460\
16534668049886272327917860857843838279679766814541009538837863609506\
80064225125205117392984896084128488626945604241965285022210661186306\
74427862203919494504712371378696095636437191728746776465757396241389\
08658326459958133904780275900994657640789512694683983525957098258226\
20522489407726719478268482601476990902640136394437455305068203496252\
45174939965143142980919065925093722169646151570985838741059788595977\
29754989301617539284681382686838689427741559918559252459539594310499\
72524680845987273644695848653836736222626099124608051243884390451244\
13654976278079771569143599770012961608944169486855584840635342207222\
58284886481584560285060168427394522674676788952521385225499546667278\
23986456596116354886230577456498035593634568174324112515076069479451\
09659609402522887971089314566913686722874894056010150330861792868092\
08747609178249385890097149096759852613655497818931297848216829989487\
22658804857564014270477555132379641451523746234364542858444795265867\
82105114135473573952311342716610213596953623144295248493718711014576\
54035902799344037420073105785390621983874478084784896833214457138687\
51943506430218453191048481005370614680674919278191197939952061419663\
42875444064374512371819217999839101591956181467514269123974894090718\
64942319615679452080951465502252316038819301420937621378559566389377\
87083039069792077346722182562599661501421503068038447734549202605414\
66592520149744285073251866600213243408819071048633173464965145390579\
62685610055081066587969981635747363840525714591028970641401109712062\
80439039759515677157700420337869936007230558763176359421873125147120\
53292819182618612586732157919841484882916447060957527069572209175671\
16722910981690915280173506712748583222871835209353965725121083579151\
36988209144421006751033467110314126711136990865851639831501970165151\
16851714376576183515565088490998985998238734552833163550764791853589\
32261854896321329330898570642046752590709154814165498594616371802709\
81994309924488957571282890592323326097299712084433573265489382391193\
25974636673058360414281388303203824903758985243744170291327656180937\
73444030707469211201913020330380197621101100449293215160842444859637\
66983895228684783123552658213144957685726243344189303968642624341077\
32269780280731891544110104468232527162010526522721116603966655730925\
47110557853763466820653109896526918620564769312570586356620185581007\
29360659876486117910453348850346113657686753249441668039626579787718\
55608455296541266540853061434443185867697514566140680070023787765913\
44017127494704205622305389945613140711270004078547332699390814546646\
45880797270826683063432858785698305235808933065757406795457163775254\
20211495576158140025012622859413021647155097925923099079654737612551\
76567513575178296664547791745011299614890304639947132962107340437518\
95735961458901938971311179042978285647503203198691514028708085990480\
10941214722131794764777262241425485454033215718530614228813758504306\
33217518297986622371721591607716692547487389866549494501146540628433\
66393790039769265672146385306736096571209180763832716641627488880078\
69256029022847210403172118608204190004229661711963779213375751149595\
01566049631862947265473642523081770367515906735023507283540567040386\
74351362222477158915049530984448933309634087807693259939780541934144\
73774418426312986080998886874132604721569516239658645730216315981931\
95167353812974167729478672422924654366800980676928238280689964004824\
35403701416314965897940924323789690706977942236250822168895738379862\
30015937764716512289357860158816175578297352334460428151262720373431\
46531977774160319906655418763979293344195215413418994854447345673831\
62499341913181480927777103863877343177207545654532207770921201905166\
09628049092636019759882816133231666365286193266863360627356763035447\
76280350450777235547105859548702790814356240145171806246436267945612\
75318134078330336254232783944975382437205835311477119926063813346776\
87969597030983391307710987040859133746414428227726346594704745878477\
87201927715280731767907707157213444730605700733492436931138350493163\
12840425121925651798069411352801314701304781643788518529092854520116\
58393419656213491434159562586586557055269049652098580338507224264829\
39728584783163057777560688876446248246857926039535277348030480290058\
76075825104747091643961362676044925627420420832085661190625454337213\
15359584506877246029016187667952406163425225771954291629919306455377\
99140373404328752628889639958794757291746426357455254079091451357111\
36941091193932519107602082520261879853188770584297259167781314969900\
90192116971737278476847268608490033770242429165130050051683233643503\
89517029893922334517220138128069650117844087451960121228599371623130\
17114448464090389064495444006198690754851602632750529834918740786680\
88183385102283345085048608250393021332197155184306354550076682829493\
04137765527939751754613953984683393638304746119966538581538420568533\
86218672523340283087112328278921250771262946322956398989893582116745\
62701021835646220134967151881909730381198004973407239610368540664319\
39509790190699639552453005450580685501956730229219139339185680344903\
98205955100226353536192041994745538593810234395544959778377902374216\
17271117236434354394782218185286240851400666044332588856986705431547\
06965747458550332323342107301545940516553790686627333799585115625784\
32298827372319898757141595781119635833005940873068121602876496286744\
60477464915995054973742562690104903778198683593814657412680492564879\
85561453723478673303904688383436346553794986419270563872931748723320\
83760112302991136793862708943879936201629515413371424892830722012690\
14754668476535761647737946752004907571555278196536213239264061601363\
58155907422020203187277605277219005561484255518792530343513984425322\
34157623361064250639049750086562710953591946589751413103482276930624\
74353632569160781547818115284366795706110861533150445212747392454494\
54236828860613408414863776700961207151249140430272538607648236341433\
46235189757664521641376796903149501910857598442391986291642193994907\
23623464684411739403265918404437805133389452574239950829659122850855\
58215725031071257012668302402929525220118726767562204154205161841634\
84756516999811614101002996078386909291603028840026910414079288621507\
84245167090870006992821206604183718065355672525325675328612910424877\
61825829765157959847035622262934860034158722980534989650226291748788\
20273420922224533985626476691490556284250391275771028402799806636582\
54889264880254566101729670266407655904290994568150652653053718294127\
03369313785178609040708667114965583434347693385781711386455873678123\
01458768712660348913909562009939361031029161615288138437909904231747\
33639480457593149314052976347574811935670911013775172100803155902485\
30906692037671922033229094334676851422144773793937517034436619910403\
37511173547191855046449026365512816228824462575916333039107225383742\
18214088350865739177150968288747826569959957449066175834413752239709\
68340800535598491754173818839994469748676265516582765848358845314277\
56879002909517028352971634456212964043523117600665101241200659755851\
27617858382920419748442360800719304576189323492292796501987518721272\
67507981255470958904556357921221033346697499235630254947802490114195\
21238281530911407907386025152274299581807247162591668545133312394804\
94707911915326734302824418604142636395480004480026704962482017928964\
76697583183271314251702969234889627668440323260927524960357996469256\
50493681836090032380929345958897069536534940603402166544375589004563\
28822505452556405644824651518754711962184439658253375438856909411303\
15095261793780029741207665147939425902989695946995565761218656196733\
78623625612521632086286922210327488921865436480229678070576561514463\
20469279068212073883778142335628236089632080682224680122482611771858\
96381409183903673672220888321513755600372798394004152970028783076670\
94447456013455641725437090697939612257142989467154357846878861444581\
23145935719849225284716050492212424701412147805734551050080190869960\
33027634787081081754501193071412233908663938339529425786905076431006\
38351983438934159613185434754649556978103829309716465143840700707360\
41123735998434522516105070270562352660127648483084076118301305279320\
54274628654036036745328651057065874882256981579367897669742205750596\
83440869735020141020672358502007245225632651341055924019027421624843\
91403599895353945909440704691209140938700126456001623742880210927645\
79310657922955249887275846101264836999892256959688159205600101655256\
375676

[свернуть]

Интереснее конечно же посчитать оптимизированной программой на ассемблере для разных ретропроцессоров по формуле Мачина, или иной, более быстрой.
PS. Вероятно первым ретропроцессором, в железе, а не в эмуляторах, на котором я проверю скорость формулы Мачина, станет R65С02P4 (Rockwell) на новоделе Apple I. от MDesk.