Формула Бейли — Боруэйна — Плаффа, която позволява извличането на всяка конкретна шестнадесетична или двоична цифра от числото пи, без да се изчисляват предишните (настоящият рекорд е постигнат с алгоритма на Чудновски, вижте под кат).
Вычислителният клъстер Google Compute Engine за 121 дни на 25 виртуални машини изчисли най-голямото количество цифри в числото пи, поставяйки нов световен рекорд: 31,4 триллиона знака след десетичната запетая. Това е първият път, когато за изчисление на такова голямо число е използвано публично облачно софтуерно решение.
Рекордът ще бъде записан на името на Емма Харуки Ивао (Emma Haruka Iwao) от подразделението за високомощностни изчисления в Google. Именно тя е използвала инфраструктурата на Google Cloud за разчетите. Предишният световен рекорд беше поставен от Питър Труб в 2016 година, когато той изчисли числото до 22,4 триллиона цифри. който също е бил спонсориран от работодателя.
Подобно на Труб, инженерът от Google приложи за изчислението y-cruncher. Тази програма използва бърз алгоритъм за изчисление на числото пи. Още в 80-те години самите с негова помощ изчислиха милиард знака след десетичната запетая.
Алгоритъмът от своя страна е основан на свойството на бързата събираемост на хипергеометричните редици:
Емма Харука Ивао се запали по "магическото" число, след като научи за него на урок по математика в училище. Wired. В университета един от нейните професори, Дайсуке Такахаси (Daisuke Takahashi), беше рекордьорът по брой изчислени цифри от числото с помощта на суперкомпютър. Днес рекорд може да постави практически всеки заинтересован инженер, който има достъп до сериозни изчислителни ресурси и голямо дисково хранилище (за съхранение на резултатите от изчисленията). Създадената през 2009 година програма е предназначена за изчисление на математически константи, като пи. Тя поддържа масивно многопоточност и трилионни диапазони. Тази програма фактически комодитизира изчисленията на константи.
«Нужен наистина мощен компютър, за да се счупи световният рекорд, — казва Ивао. — Не можеш да го направиш с компютър от магазина, затова хората преди строяха персонализирани машини». През септември 2018 г. Ивао започна да разглежда как технически ще работи процесът на изчисление извън рекордния диапазон. Веднага стана ясно, че основният проблем ще бъде обемът на данните за съхранение. В крайна сметка изчисленият резултат заема 170 терабайта. Вместо да сглобява персонализиран сървър, както са правили предшествениците й, тя използва инфраструктурата на Google Cloud.
Ивао стартира 25 виртуални машини: «Но вместо да натискам бутона за виртуална машина 25 пъти, аз го автоматизирах, — обяснява тя. — Можеш да го направиш за няколко минути, но ако ти трябва толкова много компютри, ще отнеме няколко дни, за да настроиш всичко». След това непрекъснато в продължение на 121 дни Ивао управляваше работата на y-cruncher на тези 25 виртуални машини.
За да бъдат коректни изчисленията, виртуалните машини трябваше да работят постоянно. Инженерът инсталира мониторингова система, която щеше да я предупреди, ако нещо не тръгне добре, например, за внезапен срив на една от виртуалните машини. Само един инцидент — дори за няколко минути — можеше да постави под заплаха целия процес на изчисление, ако не беше резервното копие.
«В cruncher и Google Cloud има системи за резервно копие и аз ги настроих така, че да можеш мигновено да правиш копия на тези дискове, без да спираш изчисленията», — казва Ивао. Тези данни след това се копираха и съхраняваха извън, на други дискове, под формата на моментални снимки.
«Първоначално имаше няколко параметри, които промених, например, колко данни можеш да четеш или пишеш наведнъж, и как границите ще се променят с увеличаването», — казва Ивао.
С увеличаването на броя на цифрите размерът на файловете нарастваше, а сложността на изчисленията се увеличаваше нелинейно. Това значително усложни първоначалното изчисление, когато Ивао опитваше да изчисли какъв ресурс на виртуалните машини ще й бъде необходим за проекта.
Сега приключиха изчисленията и проверката на резултата: в y-cruncher са ingebredени два основни алгоритъма — един за изчисляване на самото пи и друг за проверка. Алгоритъмът за проверка работи паралелно с изчислението, но изчислява само една цифра, така че рекордът може да се регистрира официално.
Теоретично, нов световен рекорд може да бъде поставен, ако просто вземете предишния файл и приложите формулата на Бейли — Борувина — Плаф за изчисляване на още едно число. Но със сигурност това противоречи на правилата за регистрация на подобни световни рекорди: най-вероятно всеки претендент трябва да започне изчисленията отначало. Алтернатива: да подобри предишното постижение с N%, което по формулата на Бейли — Борувина — Плаф не може да се постигне.
Източник: habr.com
