大数的实现心得

February 22, 2013 19:23


JZlib,自己练习用一个C++库, 这两天为其实现了Bignum大数类,目前只支持整型,浮点还没写。。

这两天,了解了一些实现方法: 把字符直接转换成字符串,然后使用读书时便学会的计算方法进行计算求值,开始时我就准备用这种方式。。。 不过感觉有些蛋疼,就没弄了。。。。

然后就是使用二进制,使用和计算机相同的方式来实现,这个。。我只想过,开始时还真不知如何下手,基础差, 没办法。。

然后就是后来了解到的,使用N进制来实现,二进制一位只可以表示0和1,那我用我熟悉的10之类的来表示, 于是我上面的那个大数类,便使用了10,000,000,000进制,每一个进制使用一个long long来表示。。。 然后折腾一天,终于弄出来了。。

加法减还好,直接对着位加减,进位,使用已经非常熟悉的笔算来玩。。 加法有负数时,直接调用减法,减一个负数时,直接调用加法,这样就不用去想正负什么的了。。 小的减大的还是得关心一下正负

然后就是蛋疼的乘除法了,乘法,有些麻烦,笔算乘法运算:

      1 2 3
    * 1 2 3
------------
      3 6 9
    2 4 6
+ 1 2 3
------------
  1 5 1 2 9

真要用代码写出来,略麻烦,略蛋疼,不过还好还好 最后就是痛苦的除法了,说话,既然是整数除法,最简单的不过是一直减啊减啊减啊,减到减不了为止, 减了的次数就是结果了。

上面开玩笑哈(其实我也有过这想法。。。),32, 64位的数怎么减还有个底(虽然也很慢,反正我没试过)。。。 大数这里么,要减上个十的几十上百次方的次数,剩至更多,那等算完不知道什么时候了,而用笔算,感觉太麻烦了, 然后又去网上找资料,最后发现,二进制是多么的美好,永远只有0和1。求值的时候不用去考虑更多的结果, 而我想当然使用的进制越大越好的想法,在我使用后发现效率是非常低的,特别在一些情况下,直接就卡到了, 这会也开始有点懂了,不过由于已经完成了大半的代码,不忍在此时放弃,接着写完了

以后有时间,再改成使用二进制实现,加上浮点数什么的。。

Comments: