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

[ivagor]

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

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

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

[litwr]

3ачахла тема. Никто железом не помогает... Но вот случилась оказия прогнать коммодорскую программу на бийбе (ВВС Микро) с вторым процессором 6502 на 4 МГц - такие штамповали массово с 1985-86. 100 знаков за 0.78 сек. Для бийбов делали тогда же ещё и платы на z80 6 МГц и без задержек.
На ВВС с середины 80-х ставили именно Rockwell 6512.

[Advertiser]

[litwr]

А вот ссылка на всех Мачинов в калькуляторе. Там Мачин быстрее шпигота на 5000, но чуть-чуть - http://sense.net/~egan/hpgcc/#Exampl...%80%20Shootout

[perestoronin]

Там Мачин быстрее шпигота на 5000, но чуть-чуть

В том-то и прелесть всяких разложений и хитрых алгоритмов, что они позоляют выжать из процессора все, на что он способен.
А измерять производительность алгоритмов на Васиках, калькуляторах и тем более на Жабе (Java) - особой пользы, как и разницы в скорости - не заметить никак
А что касается 6502 и "русского обгрзызка" - то м.с. 1404 все еще в пути, как приедут - может и дособираю Обгрызок-1 и тогда посмотрим на что годен Эппл-1.

[LeoN65816]

Дайте, пожалуйста, "наводку" на 6502-реализацию какого-либо из этих алгоритмов. Попробую на АГАТе прогнать.

[perestoronin]

Дайте, пожалуйста, "наводку" на 6502-реализацию какого-либо из этих алгоритмов. Попробую на АГАТе прогнать.

Процитирую текст под спойлером первого поста:

Индексатор ссылок на ресурсы с исходниками некоторых других реализаций вычисления числа Пи
http://www.pi314.net/eng/programmes.php

На процессорах 6502:

На форуме 6502 в топике http://forum.6502.org/viewtopic.php?f=2&t=2239 есть архивчики для процессоров 6500 и 6502:
http://forum.6502.org/download/file....62659b6ca3a9f8
http://forum.6502.org/download/file....62659b6ca3a9f8

Интересно, как долго будет считаться число Пи на Денди