2012吧 关注:1,631,153贴子:88,218,729

一种计算整数平方根的简单算法

只看楼主收藏回复

一楼给百度


回复
1楼2018-06-18 07:15
    关于SEG以及相关理论的研究和实验仍然在继续。
    而且,实验在不断的改进过程中,越来越倾向于支持现在的理论。
    反过来理论也提供了实验改进的具体方向。


    总的来说,整个过程正在以正反馈方式进行着。


    回复
    2楼2018-06-18 07:17
      原来关于虚数单位等问题的那个帖子以后会继续更新,带着实验设备的照片或者实验过程的视频。


      现在要说的,仍然是一个数学问题,或者说一个数学发现。
      因为这个发现可以用比较少的文字说清楚,而且内容相对独立,所以不必放在那个帖子里面。


      但是,一些基本概念会用得到。


      回复
      3楼2018-06-18 07:19
        现在考虑这样一个问题:
        i是计数极限,那么,1/i是什么?
        显然,它也是一个极限,它是有限计数器的最小可分辨的计数单位。
        也就是说,大于或者等于这个数,就不是0。


        什么意思呢?意思是,那些小于这个数的,就会被认为是0.
        比如对于100为极限的有限计数器,1/100是最小可分辨的单位,
        而1/101(显然也没法写出,因为有限计数器不能数到101),
        对于它而言,就是0了。


        这有点像是,对于浮点数做相等比较的时候由于浮点数在小数位数很多的时候,后面的小数很难说都对得上,
        那么两个浮点数若比较它们相等,则必须忽略很后面的几位小数,也就是说,把二者求差,若差的绝对值,
        大于某个比较小的数(比如10的负6次方),就认为它们相等。


        而这个比较小的数,通常叫做epsilon,埃普西隆。


        1/i,或者这里的1/100,也叫做网孔。意思是,如果一个数比它还小,就会从这个网中落出去。


        回复
        5楼2018-06-18 07:31
          这是4楼被删的部分:


          回复
          6楼2018-06-18 07:34
            上面提到了,对于能力上限为100的有限计数器,
            根本写不出
            1/101
            这种东西,如果写出了,它就是0。那么,能写出什么呢?
            我们其实只能用1和100,
            那么,能写出的就是
            1/(100+1/100)
            或者
            1/(100+1/(100+100))
            等等这些东西,总是可以把最里面的分母,写成100+1/100,而其中分数部分,100这个分母,又可以被写成100+1/100。
            如果你仔细看,它其实就是连分数。


            这个值显然已经略小于1/i,所以它就是实际上的0。
            连分数的构造方式显然是递归的,所以,为了保持连分数的每个递归周期都有一样的形式,我们把100再加上,就得到了,


            100+1/(100+1/(100+1/(100+ ...


            那么它的意思,就是 在有限计数器的计数极限100之上,再加一个0。(因为后面那些都已经落到网口之外,所以
            叫做0)。


            回复
            7楼2018-06-18 07:41
              如果说
              x+1/x
              已经超过了极限,到达下一个周期的开始,那么,一个完整周期的最大长度,就是
              x+1/(x+1/(x+...


              我们用递归方式写一个循环节:
              x' = x+ 1/x
              x=x'

              一个循环节是从x导出x'的过程,下一个循环节开始之前,令新的x等于原来的x‘


              如果你研究连分数,你会发现,若每个层次的x都取1(x'继承于上一个层次),
              那么,我们得到的是
              y=1+1/(1+1/(1+1/(


              1.6180339887...


              这个数你可能不熟悉,但是,减去1之后,你一定认识:它就是所谓的黄金分割率。
              其实,0.618的黄金分割率,正是它的倒数(也是减去1的结果)。


              什么意思呢?意思是,当有限计数器的计数能力上限为1(它就能数一个数,多一个都不能),
              它的完整周期长度为1.61803....


              不妨假定一下:为什么黄金分割率会引起美感?
              可以这么说,因为它意味着“完整”,或者说“完美“。


              回复
              8楼2018-06-18 07:50
                这是一个突破口,这种连分数形式的最简单情况,可以直接导出黄金分割率。


                这不是什么稀奇的事情,是大家早就知道的事情。
                下面这个也不稀奇:


                若令x=2,就可以得到
                2+1/(2+1/(2+1/(...
                = 2.41421356237309...


                这数似乎也不特别。但是,如果你不看2,只看后面的小数,你会想起什么?
                或者说,你把它减去1,会想起什么?


                对了,就是根号2。


                对整数部分减去1,是一种方法,其实还有一种理解,就是对整数部分除以2,因为整数除法的结果还是整数(通常计算机高级语言对整数除法的处理方式),所以1.618中的1除以2,等于0,2.414中的2除以2等于1。
                不用减去1而是用除以2,是因为,看到后面之后你会发现,通行的规则是除以2,不是减去1,虽然在这两个例子上确实没法区分。



                那么,若令x=3呢?
                3+1/(3+1/(3+1/(...
                =3.30277563773199...


                这是什么我真的没有找到。所以这条路有可能走不通,但是,没有关系,可以写一个程序,测试比如前100个数的情况,看看能出什么东西。


                如果要写程序,那就有谁是函数的变量(参数)的问题,显然x可以当做变量,但不止如此,分子1也可以被换成变量。那么递归就可以写成:


                x' = x+ k/x
                x=x'



                的形式。
                那么k应该怎么取值呢?
                因为x是有限计数器的上限,k取0就没法扩展递归了,所以k的取值,应当在1到x之间,包括x,都取整数。


                这样的话,我们就可以得到一个函数,可以叫做黄金分割函数,它有两个变量,x和k(程序里面我最终用的是i和j),还有一个额外的变量,是递归(其实是迭代方法)的次数。


                double CalculateGoldenRatio(double i, double j, int N)
                {
                double r = 1.0;
                for (int c = 0; c < N; c++)
                {
                r = i + j / r;
                }
                return r;
                }


                就像这样。


                回复
                9楼2018-06-18 08:02
                  那么,调用这个函数,就需要一个两层的循环,假设我们让N就固定取1000的话(否则还得多一层循环)。

                  for (int i = 1; i < 32; i++)
                  {
                  for (int j = 1; j <= i; j++)
                  {
                  double gr = CalculateGoldenRatio(i, j, 1000)
                  }
                  }
                  现在可以通过printf(看你用什么语言,我其实用的是C#)把这些gr都打印出来,看看有什么规律。


                  下图就是输出的结果,






                  回复
                  10楼2018-06-18 08:08
                    看到了吧,除了0之外,它是黄金分割率。
                    i为计数的时候,没有什么东西可以对应。
                    但i为偶数的时候,GR的值就对应于一个整数的平方根。
                    比如i等于8的时候,j等于1,GR等于8.12310...而它对应17的平方根,17的平方根是4.12310....
                    也就是说,如果把GR的整数部分除以2,和后面的小数部分拼接在一起,就正好得到17的平方根。


                    再回来看看那些对不上号的,比如i等于3的时候,对应的小括号里面缺少的正好是4,也就是2的平方。i等于5的时候,对应的小括号里面缺少的是9,也就是3的平方,i等于7的时候缺少的是16,4的平方。


                    这样看来,只要把对应关系找到,做成一个表格,那么,i和j构成的元组,一定可以对应一个整数的平方根(平方数的时候j不用考虑,只考虑i即可)。




                    收起回复
                    11楼2018-06-18 08:14
                      好了,就这么简单。


                      主要用到的函数已经给出,你可以直接抄走,用c/c++也好java或者C#,随便什么c类语言,自己跑一下程序。


                      你可能要问,原理是什么?
                      说实话我也不是很清楚。因为刚刚发现,还有没有去仔细研究。


                      但是可以知道的是,极限+0,其实就一对应到x+y,因为y在x上的投影总是0,然而无论如何,一个完整周期,都不能只是极限,周期性的存在导致最基本的维数是2维的(周期和偏移量两个维数),所以一定是一种加0的形式。


                      另外这种2n+1的形式(整数部分除以2,小数部分不变),似乎和Tao(二分之派)也有关。


                      这种算法,一点都不快!所以不要认为它在计算上有什么优势。
                      但是,它能成立,也确实意味着点什么东西。


                      也许其理论价值要远大于其实用价值吧。


                      回复
                      13楼2018-06-18 08:26
                        12楼又被莫名其妙的删除了:


                        回复
                        14楼2018-06-18 08:29
                          代码可能因为大于号和小于号的问题,被过滤了。


                          那个条件是,n大于等于c且n小于c加m。


                          回复
                          15楼2018-06-18 08:30
                            最后,如果我错了,如果你发现,在某个整数上,不能取得预期的结果,请告知,谢谢!


                            回复
                            16楼2018-06-18 08:40
                              https://github.com/yyl-20020115/GoldenRatio


                              这是本文提到的C#源码(VS2017项目)
                              在github上。


                              回复(4)
                              17楼2018-06-18 11:48