Нет не крутовато, если хочется надежности, то даже md5sum слабо, то чего уж говорить про более примитивные.Цитата:
Сообщение от ivagor
Кстати а чего крутого в этих простых функциях ? Что испугало ?
Вид для печати
Нет не крутовато, если хочется надежности, то даже md5sum слабо, то чего уж говорить про более примитивные.Цитата:
Сообщение от ivagor
Кстати а чего крутого в этих простых функциях ? Что испугало ?
Про крутость я не писал, я писал про достаточность.Цитата:
Сообщение от perestoronin
Даже md5sum не достаточно надежная, от неё все прогрессивное человечество не так давно (что такое 5 лет в нашу эпоху) отказалось в пользу как минимум sha256sum.Цитата:
Сообщение от ivagor
Цитата:
В файлах distinfo, использующихся в системе портов FreeBSD для контроля целостности исходных текстов, произошел полный переход на использование алгоритма вычисления контрольных сумм SHA-256. Это означает, что в файлах distinfo от новых пакетов MD5-суммы указываться не будут, а существующие строки с указанием MD5-сумм игнорируются.
Такое решение принято, поскольку алгоритм SHA-256 является более стойким к криптоанализу, чем MD5, а проверка сразу двух видов контрольных сумм не увеличивала бы безопасность.
Не нравится контрольной суммой, можно по старинке, хранить в листинге 100 верных чисел числа Пи и сравнивать в коде их с тем, что посчитал алгоритм. Тоже вариант :)Цитата:
Сообщение от ivagor
А можно еще, just for fun, вывести двоичное представление числа Пи в прямоугольную область в правом верхнем углу экрана, и рядом ниже выводить посчитанное по тестируемому алгоритму, глаз обычно у всех алмаз, сразу увидит где пиксели различаются.
Временно вернул умножение на 10000 по маленькой таблице, чтобы проверить сколько это дает - всего 2% с копейками.Цитата:
Сообщение от litwr
- - - Добавлено - - -
Чтобы закрыть тему влияния больших таблиц убрал еще и таблицу процедур для умножения младшего байта. Суммарный проигрыш (без большой таблицы *10000 и без таблицы процедур для умножения младшего байта) - примерно четыре с половиной процента, т.е. вклад каждой большой таблицы примерно 2 с небольшим процента.
Решил проверить насколько хороша формула с арктангенсами:
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К цифр.
Вложение 55490
Ура, нашему полку прибыло, в теме теперь есть и математики.
Неужели получим вычисление первых 100 цифр числа Пи меньше чем за доли секунды на КР580ВМ80А ?Цитата:
Сообщение от blackmirror
А нам то надо всего 0.1К цифр.Цитата:
Сообщение от blackmirror
Боюсь, что это будет львиная доля, а то и не одна. Поскольку с вычитанием у него не очень, то для деления придётся занимать все регистры, значит будет развёрнутая процедура, которая загрузит байт, вызовет функцию деления 24/16, сохранит результат. Скорее всего адресацию придётся использовать абсолютную. Еще нужны будут похожие процедуры, которые результат не сохраняют, а вычитают или добавляют к числу Pi, и в некоторых случаях корректируют несколько байт для распространения переноса. Для вывода проще всего 50 раз домножить на 100 при помощи маленькой таблички. Только по мере домножения нужно будет укорачивать обрабатываемую часть, чтобы не обрабатывать мусор в младших разрядах. А при делении наоборот, отбрасывать старшие нули, делить их конечно можно, но зачем?Цитата:
Сообщение от perestoronin
Вот этот вариант при замене типов на short правильно считает 4138 цифр. Причем большинство шортов можно заменить на беззнаковые, в т.ч. умножение и деление. Т.е. для расчета 100 и 1000 цифр там достаточно 16*16 и 16/16.
Перенес суперделение на 6502. Трудно догадаться убрать верчение лишнего байта - благодарности уважаемому ivagor'у. Вот код для истории
Примерно 460 тактов, для z80 - 840. Итог по скорости 6502 быстрее только менее 90%. В некоторых случаях z80 показывает очень хорошую эффективность. Но на z80 легко писать очень плохие коды, а очень хорошие очень тяжело. С 6502 гораздо легче и коды легко масштабировать, типа сделать 64/32-деление.Код: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
Последние данные по программам - дал им версию 1. :)
Коммодор +4 1.62 - 152.3 - 1362
Амстрад 6128 2.41 - 179.3 - 1582
Как обычно для 100, 1000 и 3000 цифр. Версия для Коммодора считает до 7680 цифр, а для Амстрада до 5536 в бейсике. Кроме того есть сырая версия для Амстрада в СР/М, которая досчитала до 8500 цифр, но может и немного побольше.
Чтобы совсем не пишнуться решил покинуть эту приятную тему. Может через месяц посмотрю, что тут случилось. Может появятся и результаты по БК, Спектрумам или даже лучшему домашнему ПК СССР Поиску? Успехов всем в пи-строительстве! :)
Конечно, вывод на экран. Под СР/М он ещё раз в 10 (!) медленнее. Зато там можно перенаправить вывод в файл как в ДОСе или Юниксе.Цитата:
Сообщение от ivagor
Если хотите сами проверить, то скачайте эмулятор, подсоедините диск и командой RUN"PI проверяйте. Выход в СР/М командой |CPM, но нужен системный диск.
Для Коммодора нужны две команды DLOAD"PI* и RUN
По последним цифрам. Алгоритм таков, что сбой накапливается. Для больших чисел можно и на диск сбрасывать. Дело автора.Цитата:
Сообщение от ivagor
Круто! :) Но в некоторых системах есть текстовые режимы...Цитата:
Сообщение от perestoronin
Для таких случаев вполне сгодится сравнение sha256sum с эталоном.Цитата:
Сообщение от litwr
- - - Добавлено - - -
Листинг бы продублировать и в виде вложения. Для удобства.Цитата:
Сообщение от litwr
Выкладывал тут версию легко масштабируемого деления для 8080, практически в стиле 6502, все в памяти. Но очень медленно.Цитата:
Сообщение от litwr
Формула 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х разрядного делителя, если делать обмен регистров. Вложение 55501
Еще наткнулся в википедии на Метод БВЕ, смысл которого в том, что слагаемые группируются сначала парами, общий множитель выносится за скобки, а оставшиеся дроби приводятся к общему знаменателю и складываются, далее пары опять объединяются и таким же образом вычисляются новые дроби. А в конце нужно будет просто поделить два очень больших числа. Можно даже на завершающих шагах не вычислять больше требуемой точности, но плавающая точка с мантиссой переменной длины это наверно будет жесть и для 100 или 1000 цифр эффекта не даст.
Что-то тут всё стихло. :( Немного пооптимизировал версию для 8086.
По IBM PC 5150 - 40.4 c на 1000 знаков,
по IBM PC 5170 (AT 6 MHz) - 8.2 cек на 1000 знаков. АТ в 5 раз почти быстрее на пи, чем ХТ. Использовал эмулятор с http://pcem-emulator.co.uk/
Кажется, что он чуть быстрее, чем следует.
Аналогичный бенчмаркнайзер на асме 65816 - "Решето Эратосфена".
Для предварительной оценки сложности вычислений можно использовать встроенный в любой 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
1000 знаков этот метод общелкивает менее чем за секунду, а вот 10000 лучше не пробывать так считать - "подвесил" машину на пару минут точно :)Код:# echo "scale=1000; 4*a(1)" | bc -l
3.141592653589793238462643383279502884197169399375105820974944592307\
81640628620899862803482534211706798214808651328230664709384460955058\
22317253594081284811174502841027019385211055596446229489549303819644\
28810975665933446128475648233786783165271201909145648566923460348610\
45432664821339360726024914127372458700660631558817488152092096282925\
40917153643678925903600113305305488204665213841469519415116094330572\
70365759591953092186117381932611793105118548074462379962749567351885\
75272489122793818301194912983367336244065664308602139494639522473719\
07021798609437027705392171762931767523846748184676694051320005681271\
45263560827785771342757789609173637178721468440901224953430146549585\
37105079227968925892354201995611212902196086403441815981362977477130\
99605187072113499999983729780499510597317328160963185950244594553469\
08302642522308253344685035261931188171010003137838752886587533208381\
42061717766914730359825349042875546873115956286388235378759375195778\
18577805321712268066130019278766111959092164201988
Скрытый текст
Код:# 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.
3ачахла тема. :( Никто железом не помогает... Но вот случилась оказия прогнать коммодорскую программу на бийбе (ВВС Микро) с вторым процессором 6502 на 4 МГц - такие штамповали массово с 1985-86. 100 знаков за 0.78 сек. Для бийбов делали тогда же ещё и платы на z80 6 МГц и без задержек.
На ВВС с середины 80-х ставили именно Rockwell 6512.
А вот ссылка на всех Мачинов в калькуляторе. Там Мачин быстрее шпигота на 5000, но чуть-чуть - http://sense.net/~egan/hpgcc/#Exampl...%80%20Shootout
В том-то и прелесть всяких разложений и хитрых алгоритмов, что они позоляют выжать из процессора все, на что он способен.Цитата:
Сообщение от litwr
А измерять производительность алгоритмов на Васиках, калькуляторах и тем более на Жабе (Java) - особой пользы, как и разницы в скорости - не заметить никак :)
А что касается 6502 и "русского обгрзызка" - то м.с. 1404 все еще в пути, как приедут - может и дособираю Обгрызок-1 и тогда посмотрим на что годен Эппл-1.
Дайте, пожалуйста, "наводку" на 6502-реализацию какого-либо из этих алгоритмов. Попробую на АГАТе прогнать.
Процитирую текст под спойлером первого поста:Цитата:
Сообщение от LeoN65816
Индексатор ссылок на ресурсы с исходниками некоторых других реализаций вычисления числа Пи
http://www.pi314.net/eng/programmes.php
На процессорах 6502:
Интересно, как долго будет считаться число Пи на Денди :)Цитата:
Сообщение от rw6hrm
Реплика Apple I, Synertek 6502 CPU @ 1.023 MHz:
1000 знаков, вычисления – 1 мин. 52 сек., вычисления + вывод на экран – 2 мин. 17 сек.
Исходник (Мэчин/Тейлор) взял по последней ссылке в предыдущем сообщении. В нем в 930 строке вместо "ldx #-1" написал "ldx #$FF", а то ассемблер ругался.
Ассемблер и линковщик взял с 6502.org (cc65 от Ullrich von Bassewitz), потому что автор исходника им пользовался - получил бинарник.
Из бинарника HEX-редактором и текстовым редактором сделал командный файл для Apple I (это текст, как если бы мы вводили данные в память компа с клавиатуры).
Этот командный файл утилитой toaiff от Mike Willegal преобразовал в AIFF звуковой файл (собрал эту утилиту для WIN32).
Звуковой файл грузим в реплику Apple I и радуемся.
Mdesk, благодарности вам за интересные результаты. Получается, что по Мачину 8-битки более чем 2 раза быстрее считают, чем по "затвору" ("шпиготу"). Что подтвердило исходное мнение уважаемого perestoronin'a. Осталось уважаемому ivagor'y перевести всё на 8080 и Вектор выдаст 100 знаков секунд за 0.7 или даже меньше. Однако, формула Стёрмера ещё быстрее и через те же арктангентсы. А если кто реализует подход Чудновских на 8-битном "камне", то должно быть ещё быстрее.
Добавлю ещё, что впечатлен тем, как в 1949 30-тонная махина компьютера Eniac с помощью четырех энтузиастов, которые выступали и в качестве внешней памяти компьютера, в течении 70 часов (без сна?) считала π до более чем 2000 знаков, что даёт примерно 17 часов на 1000 знаков. http://jerkwerks.com/pi-day-rematch-apple-ii-vs-hp-41c/
- - - Добавлено - - -
А вот немного негатива. В оригинальной статье Рабиновича и Вагона (http://citeseerx.ist.psu.edu/viewdoc...=rep1&type=pdf) по затворному алгоритму приводится программа на паскале. Она правильно считает 100 знаков, но неправильно 1000 - там какая-то ошибка, математики не довели программу... Поэтому, просьба к уважаемому Mdesk, сообщите последние 8 знаков из расчёта.
64201989Цитата:
Сообщение от litwr
Перевёл эту прогу на паскакале сначала на Бейсик АГАТа (хотел в дальнейшем перевести на асм). Прогнал в эмуле. Всегда даёт лишний (лидирующий) ноль. Для 10 посчитал 10 знаков, для 100 посчитал 102 знака, для 1000 посчитал 1019 знаков... Гдей-то глюк...Цитата:
Сообщение от litwr
9 - это 1001 цифра, получилась восточная сказка. :) По Мачину плохо, что трудно заранее определить минимальное число итераций для заданного числа цифр. И в алгоритме использовалась 256-значная система счисления, "затвор" так не может - он сразу ответ печатает, а не сначала накапливает, а потом переводит в 10-й вид.Цитата:
Сообщение от Mdesk
Сначала проще с паскалем разобраться, хороший компилятор fpc есть для всех платформ. 100 знаков считает правильно, хотя и с лидирующим нулем - всего 101 знак. А с 1000 - полная ерунда, больше половины знаков неверны. Но ваш результат совсем другой, с вставкой лишних нулей, но вроде бы с правильными прочими цифрами - что-то слегка не так перевели. Проблема с 1000 знаков в том, что нужно все переменные делать типа longint. Авторы наверное использовали паскаль, где тип integer 32-битный. Проверил на 3000 и 9000 знаков, с longint - все правильно.Цитата:
Сообщение от LeoN65816
Почти уверен, что оптимизированный "затвор", выдающий по 4 цифры за раз, быстрее исходного, хотя возможно он потребует чуть меньше памяти, 6.67 байт на цифру, вместо 7. А есть ещё "затвор без границ", но на его реализации даже спецы из HP больше 3000 знаков не смогли получить.
В https://rosettacode.org/wiki/Pi эта программка использует вспомогательную процедуру, в каком-то не совсем чистом паскале, но не работает совсем. Кстати, туда можно коды 6502, 8080, ... вставить, пока ещё не занято место.
https://www.youtube.com/watch?v=wlcG...ature=youtu.be
z80 112 MHz в действии. :)
Чегото не пойму я. https://ru.wikipedia.org/wiki/Acorn_Atom
Подключил человек из Голландии к своему Атому крутой сопроцессор и получает удовольствие от скорости и даже этим удовольствием делится. :)
http://stardot.org.uk/forums/viewtopic.php?f=44&t=8852
Кто-то ранее интересовался самым крутым 8-битным процессором 6809. Сделал и для него "затвор". Побыстрее 6502 из-за второго аккумулятора, но в целом впечатление неоднозначное. Какой-то 6809 неуклюжий: обратный порядок байт тормозит арифметику, с памятью работает медленнее, чем 6502, индексные регистры медленные, пересылка одного аккумулятора в другой занимает 6 (!) тактов, ... Если бы MOSTEC не разогнали, то уверен, что там бы сделали что-то гораздо более качественное.
http://litwr2.atspace.eu/pi/pi-spigot-benchmark.html
Есть очень необычный способ посчитать пи, использую клеточную колонию - http://pentadecathlon.com/lifeNews/2...lculators.html. Примерно миллион клеток за примерно 280 миллиардов поколений смогли посчитать 3 знака на средненьком ПК. Картинка с сайта явно высчитана на сверхмощном суперкомпьютере. На обычном на три знака ушло почти два часа при минимуме требуемой памяти 8 ГБ. Хотя другая программа справилась минут за 40. Прикрепляю свою картинку. На картинке с сайта знаки пи в верху, но сильно размазаны из-за уменьшения. Размеры этого клеточного компьютера 163841х114689, в экран не влезет. Прикрепляемая картинка уменьшена в 128 раз, цифры отчетливо видны.
Вложение 58588
При закачке на сайт картинка сменила размер и формат, поэтому прикрепляю её в zip-архиве.
Вложение 58587
С сожалением вспоминаю, что возможно моя поспешно выбранная позиция, послужила демотиватором для уважаемого ivagor'a. Интересно было бы посмотреть на 8085 коды. Это же какая-то почти уникальнось. Сам сделал на днях код для короля 8-х процессоров 6309. С двумя 16-битными и быстрыми аккумуляторами, с аппаратным делением 32-разрядных чисел и полной совместимостью с 6809 такой чип наверное позволительно так называть. Народ до сих пор свои Коко и Драконы обновляет. Хотя все несуразности 6809 также унаследованы, но с 16 битным АЛУ они почти незаметны. На "затворе-шпиготе" 6309 показал себя в 3.62 раза быстрее, чем 6809. В 6502 бы четыре аккумулятора и аппаратные умножение с делением...
Дык, у SuperCPU(65816) тоже потенциал приличный. Однако, кроме частоты этим не воспользовались...Цитата:
Сообщение от litwr
65816 - в каком-то смысле позор. Такое можно было сделать и к 77-78. В 75-м 6502 рвал 8080, а 65816 рядом с 8086 выглядит бледно. Ни новых регистров, ни даже аппаратного умножения, новых команд практически нет. В режиме 16 бит всего-то процентов на 50% быстрее изначального 6502... Команды не разогнаны как на 4510. С 6309 сравнивать не совсем корректно. 65816 - 16-разрядный процессор с 8-битной шиной данных, а 6309 8-разрядный с 16-разрядным АЛУ. Можно сравнить с 65802, которым можно было заменять на плате 6502 (так и делали с Эплами). 6309 гораздо мощнее. На 1.7 МГц, на арифметике легко обгоняет 8086 на 5 МГц. 65816/02 на арифметике примерно как 8086. 65816 может с 16 МБ памяти работать, но неуклюже. R800 (который в раза 4 быстрее z80) также 6309 проигрывает на арифметике раза в два. Не давали японцам развернуться, хотя и не засудили как NEC или MOS Technology.
Из формул Мачина наиболее замечательная для i8080 будет:
32*atan(1/10)-4*atan(1/239)-16*atan(1/515)
если считать в 100-ой системе, по такому алгоритму:
Деление на 25,103 и 239 делается по таблицам менее чем за 70 тактов на байт, а на 100 вообще делить не потребуется. Единственная сложная операция это деление на n, там получается примерно 400 тактов на байт, если делитель более 127. Но деление на n можно совместить для всех трёх слагаемых, при этом память будет требоваться для pi и трёх слагаемых. Результаты в EmuZWin для 3.5 МГц получились такие:Код:a=32/10
b=4/239
c=16/515
for n=1 to len
pi=(a-b-c)/(2n-1) ;здесь было n, что есть злобный баг
a/=100
b/=239 b/=239
c/=103 c/=103 c/=25
end for
100 цифр - 0,2 ms (=1/5 s)
300 цифр - 2 s
1000 цифр - 25 s
4000 цифр - 418 s
В архиве текст программы и картинки, большие цифры это время в кадрах. Что касается вычислений, то там только команды i8080 используются, если нигде не зевнул. Комментариев пока нету, но если кто будет допиливать для реального i8080 могу добавить.
Вложение 59403Вложение 59405Вложение 59404Вложение 59406Вложение 59402
Peзультаты - супер! Но возможно вы выложили не ту версию программы. Та, что есть, под СР/М считает неправильно 314227... - не пи. :( По адресу $8fcd высчитывается $1f2a1b42... И почему без бинарника? Использован ассемблер с некоторыми неожиданными особенностями типа CP A,5 и ADC 0 - первую инструкцию по стандарту Zilog пишут CP 5, а вторую ADC A,0.
Интересно уважаемый ivagor в курсе? С хорошей оптимизацией Вектор может перехватить лидерство. А с версией для 8085 может стать и недосигаемым.
Кстати, так до сих пор и не разобрался, как работают задержки на Спектруме. :( Вроде их нет при обращении к памяти выше $8000. У вас программа и все данные именно там. Но интересно, что происходит, если процессор обращается к памяти ниже $8000 из программы, которая выше $8000? Заранее благодарен за ответ или ссылку.
Прикольно. Неужели из топика всё же родился хоть какой-то бенч для Спекка? Хотя нет - только .asm внутри. Запилите нормальный бенч для Спекка на самом быстром алгоритме Z80! Можно будет пиписками померяться. :)Цитата:
Сообщение от blackmirror
А для заинтересовавшихся с другими процессорами хорошо бы и алгоритм на ЯВУ выложить...
Скачал код из архива, запустил в EmuZWin, вроде вычисляется Пи, в памяти тоже Пи лежит. Всё это безобразие было написано в эмуляторе (причём Z80) без всякой CP/M, выгрузить кусок памяти в двоичный файл там можно, а в другие форматы нет. На всякий случай положил картинку в архив и 4 дампа для 100, 300, 1000 и 4000 цифр, но как их преобразовать во что-то загружаемое я не знаю.Цитата:
Сообщение от litwr
Вложение 59589Вложение 59587
Самое забавное, что для большого количества цифр данный алгоритм можно еще ускорить, если и оставшееся деление(на нечётные числа которые присутствуют в разложении арктангенса) делать по таблицам, в теории можно получить ускорение в 1,5-2 раза.
У вас в исходнике на ассемблере после DIV_15: стоит LD HL,$4300, а в дампе вместо $43 - $56. Кроме того,расхождение в константах после INIT103: и INIT239: . :(
EDIT. Подставил константы из дампов и заработало! :) На Амстраде 1000 знаков за 30.8 секунд с печатью через медленный БДОС. Затвор тут в 6 раз тормознее. Но можно быть добрее и прописать константы в исходник, например, PI_LEN = PI_DIGITS/2+1+X... Еще бы убрать лишние цифры, которые, как правило, неверные.
Но в целом получилась очень хорошая программа. Так и до формул Чудновских можно дойти. :)
litwr, после DIV15 там просто индикатор прогресса, в какой-то момент я решил что лучше его разместить между строками, чем затирать цифры. А вот с INIT могут быть и проблемы, или это просто массивы куда-то переехали.
Лишней цифрой обычно оказывалась только последняя, которая живёт в одном байте с правильной предпоследней, поэтому мне было лень из разделять.
От Чудновских никаких плюшек ждать не стоит, у них тоже квадратичная сложность, и хоть за один проход они дают по 14 цифр, но там факториалы и на каждом шаге они дают десяток множителей/делителей которые не засунешь в таблицы. Два деления на 239, два на 103 еще одно на 25 и вычитания в сумме занимают меньше тактов чем одно честное деление для n>256, поэтому прорыв теперь может быть только с удвоением числа правильных цифр на каждом шаге, но не факт что это случится для менее чем 10000 цифр.
По просьбам трудящихся версия программы на Си, максимально упрощённая, но с некоторыми намёками в какую сторону оптимизировать:
Вложение 59590