Cyril Slobin (slobin) wrote,
Cyril Slobin
slobin

999 посчиталось и вывелось в десятичном виде за 12½ минут. Все 369'693'100 цифр. Предыдущие серии эпопеи здесь, здесь и дальше в комментариях.

Update: улучшил до 11 мин. 10 сек.

Это задачка не на знание алгоритмов, а на поиск инструмента, который эти алгоритмы знает лучше вас. Поэтому молоть числа возьмём библиотеку GNU MP, лучше вроде не бывает. А в качестве гуманного интерфейса к ней возьмём язык Pure, он забавный. Идеально было бы не мешать умным людям (посредством созданных ими умных программ) делать их работу, поэтому надо бы просто написать:

printf "%Zd" $ pow 9 (pow 9 9);

и праздновать победу. Если у вас это проходит, то всё, задача решена в лучшем виде. Но у меня под Windows XP она не может отхватить достаточно большого куска памяти для размещения результата в десятичном виде. Да, вообще почти всё время уходит на перевод в десятичный вид, собственно возведение в степень занимает 40 секунд.

Что делать? Понятно что. Разбиваем ответ "на глазок" на две примерно равные части и печатаем их отдельно. Всего у нас 360-с-чем-то миллионов цифр (можно посчитать на калькуляторе), значит, поделим ответ на 10^180'000'000. Первый результат в этом посте (12.5 минут) так и получился.

А потом до меня дошло (о великий царь!), что надо всё делать наоборот: поскольку библиотека явно лучше меня знает, как быстро переводить большие числа в десятичный вид, то лучше разбить число на две как можно более НЕравные части. Сделать бо́льшую из них настолько большо́й, чтобы только-только влезала в память. А дальше пускай библиотека сама думает, "ей умнее". У меня самым большим числом, которое ещё переводится в десятичный вид, оказалось 10^300'000'000 (ну, примерно). В итоге самый быстрый на сейчас ответ выглядит так:

using system;
using math;

const N = 300000000;

let p = pow 9 (pow 9 9);
let d = pow 10 N;
let a = p div d;
let b = p mod d;

let f = fopen "999.txt" "wt";
let w = "%0" + str N + "Zd";

fprintf f "%Zd" a;
fprintf f w b;

Кстати, если написать наоборот, N = 70'000'000 (маленький делитель и большое частное), то получается дольше, разница во времени деления. Никогда не знал про эту особенность. Ну и в Pure не оказалось единой операции divmod за одно действие, она бы, наверное, сэкономила бы ещё немного. Но не сильно -- основное время всё равно тратится непосредственно в printf.

... Три категории предвкушения чего-то приятного ...

Tags: tekniko
Subscribe

  • Неюзабилити

    Вот за что я не люблю сайт РЖД -- при попытке посмотреть расписание на сегодня он не показывает уже ушедших поездов. Типа всё, поезд ушёл,…

  • Bad and Ugly

    Я буду не первым, кто скажет: НЕ НАДО во всевозможных указаниях даты-времени прошедних событий "округлять"! Не надо писать "час назад", "вчера" или…

  • Терминология

    Платёжный автомат предлагает надписью на экране забрать извещение, красивым женским голосом -- квитанцию, а вылезает это из щели с надписью…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 10 comments

  • Неюзабилити

    Вот за что я не люблю сайт РЖД -- при попытке посмотреть расписание на сегодня он не показывает уже ушедших поездов. Типа всё, поезд ушёл,…

  • Bad and Ugly

    Я буду не первым, кто скажет: НЕ НАДО во всевозможных указаниях даты-времени прошедних событий "округлять"! Не надо писать "час назад", "вчера" или…

  • Терминология

    Платёжный автомат предлагает надписью на экране забрать извещение, красивым женским голосом -- квитанцию, а вылезает это из щели с надписью…