自由经济的一个bug

2010年3月9日 2 条评论

        完全的自由经济(最初意义的市场经济),假设了人是自私的,并谋求利益的最大化。在经济不受少数人控制的情况下,该经济模式的内在美感是没有人可以拒绝的,可以说在这种情况下这是人类创造的最棒的系统之一!(悲剧的是,当某些人获得足够的权力,他们会试图控制经济,同样也是为了其利益的最大化!)

        自由经济还有一个假设——资源是有限的。好吧,这一假设导致了一个bug——在没有其他制约的情况下,它不可避免的导致资源的枯竭!

        分析:其实很好理解,因为资源总会有稀缺的时候,当资源稀缺的时候,价格势必上涨,上涨的价格会使更多“开采”,虽然开采的量还是很少,但是开采的人却很多!价格会持续上涨,“敦促”人们把资源耗尽,最终资源枯竭!对于一般的资源,这或许没什么。但是,对于生态资源,这个问题就严重了。人类同样是生态系统的一部分,如果它崩溃了,人类同样不会有好日子过!(虽然生态资源有一定再生能力,但比起人类的贪婪,这是完全可以忽略的)

        这是在完全没有任何调控和制约的情况下的,现实中当然有很多因素。但是,这种情况发生的已经不少了,因为所谓的制约因素,一般都是在问题出现以后才会跟着出现的,而现在有那么多物种已经绝迹了!地球的生态环境正在走向一个悲剧,如果我们不去约束,那么悲剧会毫无疑问的发生。非法偷猎,非法开采,过度开采……这些都是正在进行的危机!如果我们无动于衷……

        虽然人类是一种失去了才懂得珍惜的动物,但是我们失去的难道还不够多吗?

分类: 混沌 标签:

大数类,除法分析

2010年3月7日 2 条评论

        除法是这个大数类中最令我兴奋的部分,这个算法是我在某个晚上睡着前在床上想到的(记得当时我完全想错了,后来我纠正的算法,比我预想的稍微复杂一点)

        先来看第一部,移位。我假设除数为b,被除数为a,我需要对除数移位(这不是必需的,但我觉得这样做比较高效,如果你试图映射位,会给乘法带来一定的压力,而乘法运算比我实现的移位效率低一些),这也是我把传入的除数参数const去掉的原因(放心,它最后会复原的)。移位很简单,把除数的length移得和被除数一样,直接length减一下,令其等于x,则b<<=x;就搞定了。当然,x要保存的,待会儿回复过程依赖于他。

        然后是算法的核心,我们来看最高位,令a的最高位为at,b的位bt,at乘以位的权应该小于a,bt+1乘以b的权大于b。所以我用k=at/(bt+1)对商的大小进行预估,然后先把k传递给输出的对象(注意传递的权,这依赖于之前移位过程的x,k应该被传递给第x位(十进制的9位才算1位)),同时在a-=x*b对新的a进行迭代,重复该过程,直到at<bt+1成立。这个时候x自减1,同时b右移一位。接着问题又来了,这次a比b多了一位!跟刚才不一样了。但是这很简单,现在k=at*(1000000000/(bt+1));进行和上面类似的迭代,直到a降位为止(就是a,b的length相等的时候),然后就重复先前的迭代。这这两个迭代交替,直到结束!注意625行我添加的代码,这个是用来避免溢出的(溢出可能来自第二个迭代,注意到确实有可能很大),事实上我没办法证明它不会溢出,所以额外添加了这个代码(当然这没什么损失,顶多就是这代码从来不运行而已)。

         当迭代结束,我得保证b复原!(632行的if条件就是基于此的)

         迭代结束后就已经得到结果了吗?可能没有,因为我一直是预估的,我把b算大了,a算小了!所以我需要额外的最后判断,判断他们现在的真实值,也就是644行(如果除法仅仅只有这个东西,也是可以的,但是效率可想而知)。然后就是a<b了!注意到没,a就是余数!所以余数的算法也就有了,而且求余数的时候不用保存商,所以简单很多。当然注意参数,哪些东西要做返回,哪些东西不能变,这个自己传递的时候要注意。

        最后稍微看一下效率,注意迭代的次数,这是关键,好吧一般情况下,第一个迭代有50%的概率在1次内结束,平均能在5次内就结束。乘法的效率还可以。第二个迭代衰减更快。制约的因素主要是乘法的效率,注意到用到的乘法都是一般的整数乘以大数,为此我专门写了这个函数(否则用构造函数转化的话,效率就不能保证了),这个函数的效率不会比加法低多少!

***注:权,这个其实很好理解,就拿整数135,最高位1的权是100,然后3的权是10。在这里,9位整数是一个位,位的权就是位的(length-1)*10^9

分类: Cpp 标签:

大数类,算法分析

2010年3月7日 没有评论

         其实多数的算法并不复杂,只要你明白以下几点就基本没问题了:

  •       小学学过的竖式运算是我设计加法减法和乘法的主要算法,这一思想很简单
  •       注意竖式运算有位的结合性,你可以把好几位看成一个整体!因此你一下子可以处理9位!
  •       注意不要溢出,这点很重要!尤其是乘法中,因为两个单位元素的乘积很有可能溢出,因此你需要long long这样的类型来临时保存它
  •       注意,有一种情况是虽然溢出了,但是你却没有损失任何数据!因为unsigned int是32位的,9位整数只用了其30空间,你有额外的两位可以让你“溢出”,这可以使你不需要用一个额外的变量存储,比如在加法中,两个单位相加,可能超过10^9,但是它绝对不会超过4*10^9,所以你可以放心地把和赋给保存和的那个对象的位,然后你把该位/10^9的结果传递给更高的位(就是进位,竖式中的进位还知道吧),把%10^9的结果返回给自身。减法也是,需要注意的是,我的单位是unsigned,没有负数!所以不要指望用负数投机取巧!要是那一位不够, 你应该乖乖的从高位上拿下个10^9来给他用,不要以为这样就够了,万一高位上是0怎么办,那就从更高为上拿!具体看我的代码
  •       注意,乘法的特殊性,它很容易溢出,所以随时把那个单位上多余的部分转移到高位!在422行那部分我给出了代码,这个相当简单的。当然这里要注意下,因为我把原来那位上的传递给了s,不要以为我把原来那部分给吞了(刚才我自己都差点这么想,仔细一看原来是这样)。

当然,我的除法用了完全不同的算法,刚开始我试图使用移位配合减法搞定,最后我发现了一个更高效的算法,我会在另一篇文章给出完整分析

分类: Cpp 标签:

计算两圆的交点

2010年3月6日 没有评论

请保证两圆是有交点的!这个好吧,这个是给计算机用的,当然如果你想笔算,也成。

如果你试图把公式汇总,好吧,我想你不会这么干的!

变换

图

过程

分类: Math 标签:

大数类,数据结构

2010年3月5日 没有评论

        在这里我讲一下我刚实现的这个大数类的数据结构,事实上这也是整个大数类中我最感到高兴的部分之一。

        首先我用typedef unsigned unit;定义了存储的单元,unit用于存储整数的位,之所以用typedef,是为了以后变更的考虑。我为什么选择unsigned呢?

        unsigned是unsigned int(无符号整数),32位机里它的长度是32位,可以储存9个十进制位!有效利用30/32左右的空间。注意,我用一个单元存储9个十进制位!而不是一个!事实上,它可以说是一个10亿进制数,这样做相对10进制可以使空间的使用降低为1/9,而效率接近原来的9倍!

        那么,我为什么不用2^32进制呢?这样不是可以对空间完全的使用吗?确实是,我也想。但是,虽然运算没问题,但是输出是由问题的,把2^32进制以10进制输出我没有想到和给出任何高效的算法,这一点上我认为少两位是可以接受的,我不会在乎运算上这么点效率差距的。而且我在后面需要用到它单位的额外空间,因为每一位在超过10亿后,不会溢出!我只要把多余部分传递给高位就可以,而不需要用额外的变量传递,这在某种程度上提高了后面加法和减法的效率,包括后面的除法,都需要用到这“额外的空间”。

        刚说到输出问题,10进制的数,很方便的就可以以10进制输出。第一步是输出首位,这很简单,直接输出。然后是后面的10亿进制单位,我使用了函数printunit()来输出,函数接受每一个单位和10机制的位数(bit是9,之所以用bit额不是直接用9,为的是以后更改,比如64位机上,bit是类的成员变量),就能输出指定位数的10进制。函数使用了递归实现(不是非得这样),巧妙的利用求余和整除传递递归参数,当然这只是一个很基本的递归,有兴趣的话可以分析下我的代码。

       现在分析下我的存储方式,我用了unit *型的number指针,分配new unit[limit]的空间(limit也是成员变量,用于指定number指针的空间,也是为了方便以后引入可变的长度当然目前我在这里没有实现它,你有兴趣的话可以自己实现)。我在类中给出的长度是100000,一般是够了,能够提供900000位的整数了已经。

       现在来看number指针保存数据的方式,我用number[0]保存最低9位整数,number[1]保存10~18位,以此类推,成员变量length保存数据的长度,比如27位整数,length就是3,28位整数,length就是4.因为每一个单位存储9位整数!。

       然后,非常重要的一点,初始化,非常严格的初始化。所有的函数必须保证这种严格。简单的说就是如果只有21位,那么所有number空间的其余高位(第22位及以上)必须全部置为0,而且length的值必须准确无误。因为所有函数都不会校验这个东西,所有函数都假定,传递过来的参数以及构造函数都是严格的。同时,如果函数的输出也必须保证对输出的初始话是严格的!

分类: Cpp 标签: