Клас за големи числа

Почти всеки от вас сигурно се е изправял пред проблема да прави сметки с големи числа. Големи - с по няколкостотин цифри - за които няма да стигнат и най-големите вградени типове.

Тук е предлгам реализация на клас, който поддържа такива типове - HugeInt. Големината на числата е почти неограничена. (За 32 битов компилатор максималните числа са около 2^34359738368, което си е доста) Освен това като С++ клас, HugeInt предлага и всички артиметични операции като оператори и сериализация със стандартната библиотека. Така че програми, които ползват този клас, няма да са по-различни от други, които работят със вградени типове. Спокойно можем да пишем такъв код:

  1. HugeInt hi = 281;
  2. HugeInt hiPow10 = power(hi, 10);
  3. cout << hiPow10 << endl; //изписва 3069468628627004928970801
  4.  
  5. cin >> hi; //взимаме голяма стойност от клавиатурата
  6. HugeInt hiProd = hi*hiPow10; //умножаваме я по 3069468628627004928970801
  7.  
  8. hiProd+=10; //прибавяме 10
  9. hiProd*=21; //умножаваме
  10. hiProd/=12291; //делим
  11.  
  12. hiProd = sqrt(hiProd); //получаваме цялата част на корена
  13.  
  14. cout << hiProd << endl;
Както виждате класът съдържа и помощни функции: power за целочислена степен, sqrt за целочислен корен (модификация на Нютон) и habs за модул. Благодарение на тях относително лесно ще можем да модифицираме класа за дробно число с фиксирана запетая.

Когато сме поставени пред такава задача, най-лесното което ни идва на ум е да го представим като масив, където всеки елемент е цифра от представянето на числото. И наистина такава реализация се прави и поддържа лесно. Проблемът е, че тя иска много памет и работи много бавно.

За това HugeInt работи с масив от цифри в бройна система с основа процесорна дума. На 32 битов компилатор 10 в тази система ще е 4294967296 в десетична. В случая използвах алгоритмите реализирани от Кнут през 1968 и оптимизацията за целочислено делене на Мифсъд от 1970 г. Тези алгоритми се използват и на ниско ниво в стандартните библиотеки за да вземат и изпишат клавиатурата и да го вкарат във процесорна дума. Разликата тук е че когато прехвърлим големината с която разполагаме, не се връщаме на 0, както вградените типове, а просто увеличаваме големината докато има памет.

Класът е лесен и интуитивен. Тук няма да се занимавам с точната реализация на алгоритмите. (Може би ще го направя някой ден в секция алгоритми... :) ) Ще спомена само, че използвам помощния клас numstring, за да изкарам числото в десетична система като стринг.

Очаквайте (някога) подробно описание на алгоритмите на Кнут и Мифсъд.

Приложение:

 - Класът HugeInt

Автор: Борислав Станимиров