Блог

#c #largenumber

#c #largenumber

Вопрос:

Комментарии:

1. Каковы ваши навыки длинного деления?

2. @MichaelGoldshteyn: Почему? Я неправильно его преобразовал? Мой мозг не слишком хорошо работает с базами, отличными от базы 10.

3. @sth128 нет, я думаю, он подразумевает, что для преобразования строки base 10 в ваш массив base32 int требуется много навыков длинного деления

4. Я не думаю, что Майкл прав, хотя переход от base32 к base10 требует деления.

5. Определите тип bignum (динамический массив int32_t). Определите operator* и operator для типа. используйте «длинное умножение». Восстановите его из строки так же, как вы восстановили бы int32_t из строки. Вы ведь знаете, как вручную преобразовать строку в int, верно? Это работает одинаково для любого целого числа. Единственное, что вам действительно нужно, чтобы сделать int из строки, — это операторы сложения и умножения.

Ответ №1:

  bignum str_to_big(char* str) {
     bignum result(0);
     while (*str) {
         result *= 10;
         result  = (*str - '0');
         str = str   1;
     }
     return resu<
 }
  

 std::string big_to_str(bignum num) {
    std::string resu<
    do {
        result.push_back(num%10);
        num /= 10;
    } while(num > 0);
    std::reverse(result.begin(), result.end());
    return resu<
}
  

Комментарии:

1. Результат инициализации равен 0, затем измените str *= 10; на result *= 10; и str = (*str - '0'); на result = (*str - '0');

2. push_back() добавит в конце строки. Но вам нужно вставить в начале, потому что сначала вы получаете последние цифры. Или вы могли бы изменить строку в самом конце.

3. Алекс: Я делал это много-много раз, но, конечно, когда я выкладываю это в Интернет , я все путаю … (спасибо за исправления)

4. Я думаю, что на самом деле у меня нет необходимых знаний для понимания вашего кода. Не while(*str) выйдет, если ячейка не равна 1? Кроме того, насколько я могу видеть, эта функция просто преобразует строку из отдельных цифр в целое bignum число, где, как мне нужно, она превращается в массив int32, каждая ячейка которого имеет потолок INT_MAX . Эта операция слева направо на самом деле не будет работать?

5. @sth128: я работал с притворным значением, которое содержит / является массивом int32. Вы можете использовать мой алгоритм загрузки с mulbig и addbig от DPO. Все это намного проще, как только вы изучите классы / структуры. Подробнее читайте в вашей / a C книге.

Ответ №2:

Ответ №3:

 void mulbig(vector<uint32_t> amp;bignum, uint16_t multiplicand)
{
    uint32_t carry=0;
    for( unsigned i=0; i<bignum.size(); i   ) {
        uint64_t r=((uint64_t)bignum[i] * multiplicand)   carry;
        bignum[i]=(uint32_t)(ramp;0xffffffff);
        carry=(uint32_t)(r>>32);
    }
    if( carry )
        bignum.push_back(carry);
}

void addbig(vector<uint32_t> amp;bignum, uint16_t addend)
{
    uint32_t carry=addend;
    for( unsigned i=0; carry amp;amp; i<bignum.size(); i   ) {
        uint64_t r=(uint64_t)bignum[i]    carry;
        bignum[i]=(uint32_t)(ramp;0xffffffff);
        carry=(uint32_t)(r>>32);
    }
    if( carry )
        bignum.push_back(carry);
}
  

 void atobignum(const char *str,vector<uint32_t> amp;bignum)
{
    bignum.clear();
    bignum.push_back(0);
    while( *str ) {
        mulbig(bignum,10);
        addbig(bignum,*str-'0');
          str;
    }
}
  

Комментарии:

1. assume infinite space for number storage и бесконечно быстрый компьютер, чтобы можно было запускать следующую функцию… В любом случае концепция идеальна, вам просто нужно остановить ее, когда она достигнет конца массива.

2. Условие в while(*bignum || carry) неверно по отношению к *bignum . Цикл while может остановиться слишком рано, когда он достигает *bignum==0 и переносит==0 . Рассмотрим возможность умножения 0x100000000 на 2. В этом случае тело цикла вообще не будет выполняться. Вам нужно различать нулевую цифру (то есть * bignum==0) и последнюю, самую значимую цифру, что вы не можете с таким дизайном.

3. Боже. Вы, конечно, правы. Примеры, отредактированные для лучшей работы в реальном контексте, за счет некоторой скорости и использования STL.

Ответ №4:

Ответ №5:

Комментарии:

1. это звучит слишком сложно.

2. Как мне обойти ограничение в байтах int32 / int64?

3. @sth128, я не понимаю, как вы можете использовать здесь обычные целочисленные типы. Вам нужно будет определить свое собственное представление для очень больших чисел, таких как строки, или использовать другое, созданное кем-то другим, например, bignum . Мой ответ выше — полушутка — это может быть не самый эффективный способ сделать что-то, но, вероятно, его проще всего концептуализировать.

4. @Caleb: Я написал кучу функций для представления огромных чисел. Это в формате массива символов с последней ячейкой ' ' или '-' (угадайте, что они делают). Однако каждая ячейка представляет десятичную цифру с основанием 10 (например. '1234 ' означает положительное значение 1234 в базе 10). Выполнение арифметики в базе 10 происходит чрезвычайно медленно, и кто-то на этом сайте предложил мне преобразовать char массив в int32 массив, где каждая ячейка представляет базовую цифру 2 ^ 32 (`4 миллиарда) (поэтому, когда ячейка достигает 2 ^ 32, она переходит к следующей).