[問題] 自己做的大數class(解精華區2-12 Q5,6)

[wtchen (沒有存在感的人)]

開發平台(Platform): (Ex: VC++, GCC, Linux, ...) 
Lubuntu 15.04 + g++

額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 
sys/time.h

問題(Question)：

感謝各位先進對於operator overloading的指導
這是我為了解精華區2-12 問題5-6所做的class: BigNumber
問題5：
100 的 階乘是多少？
要精確到 每一位？

問題6:
強迫使用遞回呼叫的方式求 費氏數列。
第幾項： 0, 1, 2, 3, 4, 5
答案：   1, 1, 2, 3, 5, 8, 13, . . .
請問：第 100項的答案是 多少？
必須精確到 每一個 位數，
請問：你的程式 需要花多少時間完成？
精確度要 小於 0.1秒

我想直接做個可以跟一般unsigned int乘除而且能跟同class的加減應該就OK了
拙作程式碼同步分享在此：
https://gist.github.com/gnitnaw/79ccbac48a22e14b67c4
Feis大大的建議相當有用，把+-*/%放在class外的確方便很多

這邊想問個問題，我有另外為這個class覆寫<<operator
所以BigNumber a(0); cout << a << endl; 這樣是OK的。
那如果我想要讓
    BigNumber a(0), b(0); cout << a+b << endl;
也能成功，有其他辦法嗎？
(因為如果a,b是type double或int，這樣是沒啥問題的)
謝謝。

#include <vector>
#include <iostream>
#include <sstream>
#include <math.h>
#include <sys/time.h>

using namespace std;

class BigNumber {
  private :
  vector <unsigned long> blocks;
  static const unsigned long limitBlock = 10000000000;
  const unsigned int nB = log10l(limitBlock);

  public :
  BigNumber(unsigned long n){
    blocks.push_back(n%limitBlock);
    if (n>=limitBlock) blocks.push_back(n/limitBlock);
  }

  size_t getNBlocks() const {
    return blocks.size();
  }

  string getStringBlock(size_t i) const{
    stringstream ss;
    ss << blocks[i];
    string convert_str;
    ss >> convert_str;
    if (blocks.size() == 1) return convert_str;
    else {
      if (i == blocks.size()-1) return convert_str;
      else {
        if (blocks[i]==0) {
          for (unsigned int j(0); j<nB-1; ++j) {
            convert_str += "0";
          }
        } else if (convert_str.size() < nB) {
          for (unsigned int j(0); j<=(nB-convert_str.size()); ++j) {
            convert_str = "0" + convert_str;
          }
        }
      }
      return convert_str;
    }
  }

  int getNDigit() const {
    int a=0;
    for (size_t i(0); i<blocks.size(); ++i) {
      a += getStringBlock(i).size();
    }
    return a;
  }

  void print(ostream& out) const {
    for (int i(blocks.size()-1); i>=0; --i) {
      cout << getStringBlock(i);
    }
  }

  void Carry() {
    for (unsigned int i(0); i<blocks.size(); ++i){
      if (blocks[i]>=limitBlock) {
        if (i!=blocks.size()-1) {
          blocks[i+1] += blocks[i]/limitBlock;
        } else {
          blocks.push_back(blocks[i]/limitBlock);
        }
        blocks[i] = blocks[i]%limitBlock;
      }
    }
  }

  void Pop() {
    while (blocks[getNBlocks()-1] == 0) {
      blocks.pop_back();
    }
  }

  BigNumber& operator+=(const BigNumber& c) {
    while (c.getNBlocks()>blocks.size()) {
      blocks.push_back(0);
    }
    for (unsigned int i(0); i<c.getNBlocks(); ++i) {
      blocks[i]+=c.blocks[i];
    }
    Carry();
    return *this;
  }

  BigNumber& operator-=(const BigNumber& c) {
    if (c.getNBlocks()>blocks.size() || (c.getNBlocks()==blocks.size()
      and c.blocks[c.getNBlocks()-1]>blocks[getNBlocks()-1])) {
      blocks.clear();
      blocks.push_back(0);
    } else {
      for (unsigned int i(0); i<c.getNBlocks(); ++i) {
        if (blocks[i]<c.blocks[i]) {
          blocks[i+1] -= 1;
          blocks[i] += limitBlock;
        }
        blocks[i]-=c.blocks[i];
      }
    }
    Pop();
    return *this;
  }

  BigNumber& operator*=(const unsigned int n) {
    for (unsigned int i(0); i<blocks.size(); ++i) {
      blocks[i]*=n;
    }
    Carry();
    return *this;
  }

  BigNumber& operator/=(const unsigned int n) {
    if (n==0) {
      cout << "Cannot divide by 0!" << endl;
      return *this;
    }
    for (int i(blocks.size()-1); i>=0; --i) {
      if (i>0) {
        blocks[i-1] += (blocks[i]%n) * limitBlock;
      }
      blocks[i] /= n;
    }
    Pop();
    return *this;
  }
};

const BigNumber operator+(BigNumber a, const BigNumber& b) {
  a += b;
  return a;
}

const BigNumber operator-(BigNumber a, const BigNumber& b) {
  a -= b;
  return a;
}

const BigNumber operator*(unsigned int a, const BigNumber& b) {
  BigNumber c(b);
  c *= a;
  return c;
}

const BigNumber operator*(const BigNumber& b, const unsigned int a) {
  BigNumber c(b);
  c *= a;
  return c;
}

const BigNumber operator/(const BigNumber& b, const unsigned int a) {
  BigNumber c(b);
  c /= a;
  return c;
}

const BigNumber operator%(const BigNumber& b, const unsigned int a) {
  BigNumber c(b);
  c /= a;
  c *= a;
  return BigNumber(b - c);
}

ostream& operator<<(ostream&out, const BigNumber& n) {
  n.print(out);
  return out;
}

const BigNumber Fibonacci(unsigned int i);

int main(){
  struct timeval start_time, end_time;
  // 計算費式數列，用前35項得出的時間(us)推算之後第100項所需的時間
  // T(n) = T(n-1) + T(n-2)
  vector <BigNumber> Fib;
  vector <BigNumber> duration;
  cout << "Fibonacci Number : " << endl;
  cout << "N:\tFibonacci(N)\tTime of estimation (us)"<< endl;
  for (unsigned long i(0); i<=35; ++i) {
    gettimeofday(&start_time,0);
    BigNumber f = Fibonacci(i);
    gettimeofday(&end_time,0);
    duration.push_back(BigNumber(1000000*(end_time.tv_sec - start_time.tv_sec) + (end_time.tv_usec - start_time.tv_usec)));
    Fib.push_back(f);
    if (i>=2) {
      cout << i << "\t"<< f << "\t" << duration[i]<< endl;
    }
  }

  for (unsigned long i(36); i<=100; ++i) {
    Fib.push_back(Fib[i-1]+Fib[i-2]);
    duration.push_back(duration[i-1]+duration[i-2]);
    cout << i << "\t"<< Fib[i] << "\t" << duration[i] << endl;
  }

  cout << endl;

  // 計算階乘

  cout << "Factorial" << endl;
  BigNumber a(1);
  for (unsigned int i(1); i<=100; ++i) {
    a *= i;
    cout << i<<"!= "<< a << endl;
  }

  return 0;
}

const BigNumber Fibonacci(unsigned int i) {
        if (i==0) return BigNumber(0);
        if (i==1) return BigNumber(1);
        return Fibonacci(i-1)+Fibonacci(i-2);
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 90.27.173.53
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1432563848.A.099.html
→ Feis: ostream& operator<<(ostream &out, const BigNumber &n)
→ wtchen: 喔喔！我了解了，謝謝你。
※ 編輯: wtchen (90.27.173.53), 05/26/2015 00:24:26
推 softseaweed: 其實費式數列有direct function 可以不用遞回的
推 softseaweed: 抱歉 沒看到你在解任務
→ wtchen: 任務規定要用遞迴(汗)
※ 編輯: wtchen (90.27.173.53), 05/26/2015 01:42:41
→ wtchen: 精華區2-12 Q7也解了，不過因為太簡單了就不分享了
推 Killercat: 建議這種東西以後丟gist 大家會比較容易看懂
→ wtchen: 我有阿....
→ Killercat: er...我眼殘了只看到程式碼 抱歉 XD