Факториал в библиотеке bignum

Я пытался создать свою собственную реализацию библиотеки bignum. Кажется, я не могу заставить факториал работать. Если я попрошу его решить 4!, он выдаст 96. Он умножает 4 дважды. аналогично 5! это 600, а не 120. Я не реализовал деление, поэтому я не могу/не хочу делить ответ на число

//bignum project
#include <iostream>
using namespace std;

class bignum
{
      public:
      int number[100];
      int dpos;
      int operator/ (bignum);
      bignum operator- (bignum);
      bignum operator* (bignum);
      bignum operator+ (bignum);
      bignum operator= (string);     
      void output()
      {
           int begin=0;
           for(int i=0; i<=99; i++)
           {
                   if(number[i]!=0 || begin==1)
                   {
                                   cout<<number[i];
                                   begin=1;
                   }
           }
      }
};

bool num_is_zero(bignum k)
      {
           for(int a=0; a<=99; a++)
           {
                   if(k.number[a]!=0)
                   {
                                     return false;
                   }
           }
           return true;
      }

 bignum factorial(bignum a)
      {
             bignum j;
             bignum fact;
             fact="1";

             while(!num_is_zero(a))
             {
                                   j="1";
                                   fact=fact*a;
                                   a=a-j;                         
             }
             return fact;
      }

bignum bignum::operator= (string k)
{
       int l;
       l=k.length()-1;
       for(int h=0; h<=99; h++)
       {
                   number[h]=0;
       }
       for(int a=99; a>=0 && l>=0; a--)
       {
               number[a]=k[l]-'0';
               l--;
       }
}

bignum bignum::operator+ (bignum b) 
{
  bignum a;
  int carry=0;
  for(int k=0; k<=99; k++)
  {
                   a.number[k]=0;
  }
  for(int i=99; i>=0; i--)
  {
          a.number[i]= number[i]+b.number[i]+a.number[i];
          if(a.number[i]>9)
          {
                           carry=(a.number[i]/10);
                           a.number[i-1]+=carry;
                           a.number[i]=(a.number[i]%10);
          }

  }
  return (a);
}

bignum bignum::operator- (bignum c) 
{
  bignum a;
  int sign=0;
  for(int k=0; k<=99; k++)
  {
                   a.number[k]=0;
  }
  for(int i=99; i>=0; i--)
  {
          if(number[i]<c.number[i])
          {
                    number[i]+=10;
                    if(i!=0)
                    number[i-1]--;

          }
          a.number[i]=number[i]-c.number[i];
  }
  return (a);
}

bignum bignum::operator* (bignum b) 
{
  bignum ans;
  int ans_grid[100][100],x,lines=0,carry,sum[100];
  for(int a=0; a<=99; a++)
  {
          for(int b=0; b<=99; b++)
          {
                  ans_grid[a][b]=0;
          }
  }
  for(int i=99; i>=0; i--)
  {
          for(int j=i,x=99; j>=0; j--,x--)
          {       
                    ans_grid[lines][j]=(number[i]*b.number[x]);       
          } 
          lines++;        
  }

//------------------------------------------------Carry Forward and assign to ans------------------------------------------------//
  for(int j=99; j>=0; j--)
  {
          for(int i=99; i>=0; i--)
          {
                  if(ans_grid[j][i]>9 && i!=0)
                  {
                                      carry=(ans_grid[j][i]/10);
                                      ans_grid[j][i-1]+=carry;
                                      ans_grid[j][i]%=10;
                  }
          }
  } 
  for(int col=99; col>=0; col--)
  {
          for(int row=99; row>=0; row--)
          {
                  sum[col]+=ans_grid[row][col];
          }
  }
  for(int i=99; i>=0; i--)
          {
                  if(sum[i]>9 && i!=0)
                  {
                                      carry=(sum[i]/10);
                                      sum[i-1]+=carry;
                                      sum[i]%=10;
                  }
          }
  for(int l=0; l<=99; l++)
  ans.number[l]=sum[l];
//-------------------------------------------------------------------------------------------------------------------------------//
  return (ans);
}

person viraj    schedule 21.06.2011    source источник
comment
Когда вы пишете for(int a=99; a>=0,l>=0; a--), вы уверены, что имеете в виду именно это? Вы понимаете использование оператора запятой?   -  person Kerrek SB    schedule 21.06.2011
comment
Кроме того, не полагайтесь на кодировку символов ASCII. Скажите что-нибудь вроде char c = FetchChar(); unsigned int digit = c - '0';, это будет работать, если в вашей кодировке все цифры расположены в непрерывном порядке.   -  person Kerrek SB    schedule 21.06.2011
comment
@Kerrek SB Я понял, что это означает И не понял, что вы сказали о кодировке. Влияет ли это на целые числа?   -  person viraj    schedule 21.06.2011
comment
Вы поняли, что это означает это? Это забавный подход к программированию :-) Просто возьмите 4! быть 96 и все готово! Если серьезно, вы хотите, чтобы оператор && означал и. Что касается персонажей, я имею в виду вашу линию number[a]=k[l]-48; Почему 48? Это жестко запрограммированный код ASCII. Будь джентльменом и скажи '0' вместо этого!   -  person Kerrek SB    schedule 21.06.2011
comment
Наконец, есть ли причина, по которой вы не можете просто использовать libgmp? Я осмелюсь сказать, что вам будет сложно написать что-то более эффективное, чем это.   -  person Kerrek SB    schedule 21.06.2011
comment
Все это сделал. Но я все еще получаю 96. И я пишу это не для того, чтобы использовать его для другого проекта.   -  person viraj    schedule 21.06.2011
comment
@Viraj: Вы опубликуете и протестируете исправленный код?   -  person Kerrek SB    schedule 21.06.2011
comment
Я проверил это. Я отредактирую это   -  person viraj    schedule 21.06.2011
comment
Скомпилируйте со всеми предупреждениями (в gcc: -W -Wall -Wextra -pedantic) и используйте отладчик памяти для результата; Я пытаюсь, и у меня уже есть несколько жалоб.   -  person Kerrek SB    schedule 21.06.2011
comment
Я пытался скомпилировать это сам; У меня возникает соблазн утверждать, что проблема в функции умножения, не зная точной ошибки.   -  person Kerrek SB    schedule 21.06.2011


Ответы (1)


Я думаю, ваша проблема в том, что sum не инициализирован в вашем operator*. Я не хочу давать частичный ответ, так как я взял код и немного повозился с ним, поэтому вот моя версия, которая работает (и также правильно печатает «0»):

Обновление: я не мог удержаться от нескольких структурных улучшений. Я не трогал вашу процедуру умножения, поэтому вы все равно сможете извлечь исправление, даже если вам все равно.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class bignum
{
public:
  int number[100];

  bignum() { std::fill(number, number + 100, 0); }
  bignum(const bignum & other) { std::copy(other.number, other.number + 100, number); }
  bignum(const std::string &);

  bignum & operator-=(const bignum &);
  inline bignum operator-(const bignum & c) const { return bignum(*this) -= c; }
  bignum operator*(const bignum &) const;
  inline bignum & operator= (const std::string & k) { return *this = bignum(k); }

  inline operator bool() const
  {
    for (size_t a = 0; a < 100; ++a)
      if (number[a] != 0) return true;
    return false;
  }

};

std::ostream & operator<<(std::ostream & o, const bignum & b)
{
  bool begun = false;

  for (size_t i = 0; i < 100; ++i)
  {
    if (begun || b.number[i] != 0)
    {
      cout << b.number[i];
      begun = true;
    }
  }

  if (!begun) o << "0";

  return o;
}

bignum::bignum(const std::string & k)
{
  std::fill(number, number + 100, 0);
  for(size_t h = 0; h < std::min(k.length(), 100U); ++h)
    number[99 - h] = k[k.length() - 1 - h] - '0';
}

bignum & bignum::operator-=(const bignum & c)
{
  for (int i = 99; i >= 0; --i)
  {
    if (number[i] < c.number[i])
    {
      number[i] += 10;
      if (i != 0) --number[i-1];
    }
    number[i] -= c.number[i];
  }
  return *this;
}

bignum bignum::operator*(const bignum & b) const
{
  bignum ans;
  int ans_grid[100][100], lines = 0, carry, sum[100];

  std::fill(sum, sum + 100, 0);
  for (size_t i = 0; i < 100; ++i) std::fill(ans_grid[i], ans_grid[i] + 100, 0);

  for(int i=99; i>=0; i--)
    {
      for(int j=i,x=99; j>=0; j--,x--)
        {
          ans_grid[lines][j]=(number[i]*b.number[x]);
        }
      lines++;
    }

  //------------------------------------------------Carry Forward and assign to ans------------------------------------------------//
  for(int j=99; j>=0; j--)
    {
      for(int i=99; i>=0; i--)
        {
          if(ans_grid[j][i]>9 && i!=0)
            {
              carry=(ans_grid[j][i]/10);
              ans_grid[j][i-1]+=carry;
              ans_grid[j][i]%=10;
            }
        }
    }
  for(int col=99; col>=0; col--)
    {
      for(int row=99; row>=0; row--)
        {
          sum[col]+=ans_grid[row][col];
        }
    }
  for(int i=99; i>=0; i--)
    {
      if(sum[i]>9 && i!=0)
        {
          carry=(sum[i]/10);
          sum[i-1]+=carry;
          sum[i]%=10;
        }
    }
  for(int l=0; l<=99; l++)
    ans.number[l]=sum[l];
  //-------------------------------------------------------------------------------------------------------------------------------//
  return (ans);
}

bignum factorial(bignum a)
{
  bignum j; j = "1";
  bignum fact; fact="1";

  while(a)
  {
    fact = fact * a;
    a = a-j;
  }
  return fact;
}


int main(int argc, char * argv[])
{
  if (argc < 2) return 0;
  bignum a;
  a = std::string(argv[1]);
  bignum b = factorial(a);
  cout << a << std::endl << b << std::endl;
}

Назначение строки по-прежнему не работает для строк с более чем одной цифрой, но я полагаю, что это был не ваш вопрос...

person Kerrek SB    schedule 21.06.2011
comment
Запустил эту программу: #include bignum.h //код, который я вставил выше int main() { bignum k; к=43; к=к*к; к.выход(); система(ПАУЗА); вернуть 0; }' Выдает число 1849. Итак, что не так :S - person viraj; 22.06.2011
comment
Я скомпилировал, используя -W -Wall -Wextra -pedantic, и все, что я получил, это два или три предупреждения о неиспользуемых переменных. - person viraj; 22.06.2011
comment
@viraj: Без понятия. Также используйте valgrind для проверки неинициализированного доступа к памяти. Моя версия работает (почти; ваш вариант возврата назад действительно неудобен, мне нужно набрать 34, чтобы получить 43). Результат 43! 60415263063373835637355132068513997507264512000000000. - person Kerrek SB; 22.06.2011
comment
Странно, потому что когда я присваиваю строке 43, она занимает только 43. :| какой компилятор вы используете? - person viraj; 22.06.2011
comment
Единственное, что не так с моей программой, это то, что она умножает число само на себя еще раз. Не знаю, почему :| - person viraj; 22.06.2011
comment
@viraj: Извините, я допустил глупую ошибку, когда улучшил ваш код :-) Исправлено, проверьте мой конструктор из строки! Также обратите внимание, что в философии дизайна используется конструкция для реализации присваивания и += для реализации +. - person Kerrek SB; 22.06.2011
comment
Извините, но я не понял, что вы имели в виду, когда сказали: конструкция для реализации назначения. - person viraj; 22.06.2011
comment
@viraj: Вы должны иметь возможность построить bignum из строки, bignum a("123");, но вы также должны иметь возможность назначить ее: a = "456";. Чтобы избежать повторения кода, обычно оператор присваивания реализуется в терминах конструктора (используя неявно объявленный конструктор копирования). Это то, что я сделал в своем переписывании, поэтому я могу использовать как построение, так и присваивание. - person Kerrek SB; 22.06.2011
comment
Ой. Правильно, Вы не внесли никаких изменений в алгоритм умножения или факториала. Значит, проблема в другом? - person viraj; 22.06.2011
comment
@Viraj: Ну, я исправил алгоритм умножения, инициализировав sum, но в остальном я его не менял. Что я изменил, так это дизайн bignum class. Но вы можете просто сравнить их и посмотреть, что я сделал. - person Kerrek SB; 22.06.2011