Euler Project 挨个做- 之二 (Q51-Q78)

tree_new_bee

不得已动用google大爷， 搜到的算法， 不过依然是搞不明白其中的道理：

with t0 as (select 23 num from dual)
,t(r, n, fz,fm, path) as (
select 1, num, 1, trunc(sqrt(num)), cast(',' as varchar2(4000)) from t0 where trunc(sqrt(num))<>sqrt(num)
union all
select r+1,n, (n-fm*fm)/fz,  trunc((sqrt(n) + fm )/((n-fm*fm)/fz))*((n-fm*fm)/fz)-fm,
path || fz||'/'||fm||','
from t where r<=50  and instr(path,','||fz||'/'||fm ||',')=0
)
--select r,n,fz,fm, path,trunc(fz/(sqrt(n)-fm)), length(translate(path, ','||path, ','))-1 len from t
select n, max(length(translate(path, ','||path, ','))-1) from t group by n

        N MAX(LENGTH(TRANSLATE(PATH,','|
---------- ------------------------------
        23                              4

[ 本帖最后由 tree_new_bee 于 2011-1-6 10:48 编辑 ]

newkid

小数部分：(B*SQRT(N)-C)/D
倒数：D/(B*SQRT(N)-C)
为了消除分母根号，上下同时乘以(B*SQRT(N)+C)

用你的办法确实快了一半：
CREATE OR REPLACE FUNCTION F_SQRT (N NUMBER) RETURN NUMBER
AS
  A NUMBER;
  B NUMBER;
  C NUMBER;
  D NUMBER;
  A2 NUMBER;
  B2 NUMBER;
  C2 NUMBER;
  D2 NUMBER;
  GCD NUMBER;
  STR VARCHAR2(4000);
  STR2 VARCHAR2(1000);
  
BEGIN
  A:=TRUNC(SQRT(N));
  B:=1;
  C:=A;
  D:=1;
  STR :='~'|| A||','||B||','||C||','||D||'~';
  
  LOOP
    --- 分子=D*(B*SQRT(N)+C) = D*B*SQRT(N)+D*C
    --- 分母=(B*SQRT(N)-C)*(B*SQRT(N)+C) = B*B*N - C*C
   
    A2 := TRUNC((D*B*SQRT(N)+D*B*C)/(B*B*N - C*C));
    B2 := D*B;
    C2 := A2*(B*B*N - C*C) - D*C;
    D2 := (B*B*N - C*C);

    A := A2;
    B := B2;
    C := C2;
    D := D2;   
   
    GCD := B;

        IF MOD(B,GCD)=0 AND MOD(C,GCD)=0 AND MOD(D,GCD)=0 THEN
           B := B/GCD;
           C := C/GCD;
           D := D/GCD;
        END IF;   

    STR2 := A||','||B||','||C||','||D||'~';
    IF INSTR(STR,'~'||STR2)>0 THEN
       -- DBMS_OUTPUT.PUT_LINE(STR);
       STR := SUBSTR(STR,INSTR(STR,'~'||STR2)+1);
       RETURN LENGTH(STR)-LENGTH(REPLACE(STR,'~'));
    END IF;
    STR := STR||STR2;
  END LOOP;
  DBMS_OUTPUT.PUT_LINE('ERROR: N='||N);
END;
/

SELECT COUNT(*)
   FROM (SELECT F_SQRT(LEVEL) f
           FROM DUAL
          WHERE MOD(SQRT(LEVEL),1)<>0
          CONNECT BY LEVEL<=10000
        )
WHERE MOD(f,2)=1;

  COUNT(*)
----------
      1322

Elapsed: 00:00:03.62

newkid

修改后的SQL能出来了虽然还是很慢：
WITH n AS (SELECT LEVEL N FROM DUAL WHERE MOD(SQRT(LEVEL),1)>0 CONNECT BY LEVEL<=10000)
,t(A,B,C,D,STR,GCD,N) AS (
SELECT TRUNC(SQRT(N)),1,TRUNC(SQRT(N)),1,CAST('~' AS VARCHAR2(4000)),0,N FROM n
UNION ALL
SELECT CASE WHEN GCD=0 THEN TRUNC((D*B*SQRT(N)+D*B*C)/(B*B*N - C*C)) ELSE A END
      ,CASE WHEN GCD=0 THEN D*B
            WHEN MOD(B,GCD)=0 AND MOD(C,GCD)=0 AND MOD(D,GCD)=0 THEN B/GCD
            ELSE B
       END
      ,CASE WHEN GCD=0 THEN TRUNC((D*B*SQRT(N)+D*B*C)/(B*B*N - C*C))*(B*B*N - C*C) - D*C
            WHEN MOD(B,GCD)=0 AND MOD(C,GCD)=0 AND MOD(D,GCD)=0 THEN C/GCD
            ELSE C
       END
      ,CASE WHEN GCD=0 THEN B*B*N - C*C
            WHEN MOD(B,GCD)=0 AND MOD(C,GCD)=0 AND MOD(D,GCD)=0 THEN D/GCD
            ELSE D
       END
      ,CASE WHEN GCD=0 THEN STR||A||','||B||','||C||','||D||'~' ELSE STR END
      ,CASE WHEN GCD=0 THEN D*B ELSE 0 END
      ,N
  FROM t
WHERE INSTR(STR,'~'||A||','||B||','||C||','||D||'~')=0   
) CYCLE A,B,C,D,GCD,N SET cycle_flag TO 'Y' DEFAULT 'N'
SELECT COUNT(*)
  FROM (SELECT N,SUBSTR(STR, INSTR(STR,'~'||A||','||B||','||C||','||D||'~')+1) AS STR
          FROM T
         WHERE INSTR(STR,'~'||A||','||B||','||C||','||D||'~')>0
       )
WHERE MOD(LENGTH(STR)-LENGTH(REPLACE(STR,'~')),2)=1
;

  COUNT(*)
----------
      1322

Elapsed: 00:00:56.89

GOOGLE的算法你慢慢玩吧！为什么有个迭代次数 r<=50？

tree_new_bee

很奇怪。
用上上面111#楼的方法， 计算10000以内的数没问题(9000都没问题)， 但计算10000就会出ORA-07445错误。


with t0 as (select rownum num from dual connect by rownum<=9000)
,t(r, n, fz,fm, path) as (
select 1, num, 1, trunc(sqrt(num)), cast(',' as varchar2(4000)) from t0 where trunc(sqrt(num))<>sqrt(num)
union all
select r+1,n, (n-fm*fm)/fz,  trunc((sqrt(n) + fm )/((n-fm*fm)/fz))*((n-fm*fm)/fz)-fm,
path || fz||'/'||fm||','
from t where r<=500  and instr(path,','||fz||'/'||fm ||',')=0
)
--select r,n,fz,fm, path,trunc(fz/(sqrt(n)-fm)), length(translate(path, ','||path, ','))-1 len from t
,tperiod as (select n, max(length(translate(path, ','||path, ','))-1) len from t group by n)
--select * from tperiod
select count(*) from tperiod where mod(len,2)=1

  COUNT(*)
----------
      1194

Executed in 17.421 seconds


改成10000后， 没反应。强行终止后， alert.log中会出现：
ORA-07445: 出现异常错误: 核心转储 [kditpin()+37] [ACCESS_VIOLATION] [ADDR:0x0] [PC:0x28CBD93] [UNABLE_TO_READ] []
ORA-01013: 用户请求取消当前的操作

同时，这个操作，把我的temp表空间从几百兆扩到了8G.

[ 本帖最后由 tree_new_bee 于 2011-1-6 11:21 编辑 ]

tree_new_bee

原帖由 newkid 于 2011-1-6 10:51 发表


GOOGLE的算法你慢慢玩吧！为什么有个迭代次数 r

没用。 怕算法有失误导致无限迭代， 让它有终止的机会而已。 后来没去掉。

tree_new_bee

为了绕过bug. 我把10000分成两段算：

with t0 as (select level num from dual connect by level<=7000)
,t1 as (select level num from dual where level>7000 connect by level<=10000)
,ta(r, n, fz,fm, path) as (
select 1, num, 1, trunc(sqrt(num)), cast(',' as varchar2(4000)) from t0 where trunc(sqrt(num))<>sqrt(num)
union all
select r+1,n, (n-fm*fm)/fz,  trunc((sqrt(n) + fm )/((n-fm*fm)/fz))*((n-fm*fm)/fz)-fm,
path || fz||'/'||fm||','
from ta where instr(path,','||fz||'/'||fm ||',')=0
)
,tperioda as (select n, max(length(translate(path, ','||path, ','))-1) len from ta group by n)
,tb(r, n, fz,fm, path) as (
select 1, num, 1, trunc(sqrt(num)), cast(',' as varchar2(4000)) from t1 where trunc(sqrt(num))<>sqrt(num)
union all
select r+1,n, (n-fm*fm)/fz,  trunc((sqrt(n) + fm )/((n-fm*fm)/fz))*((n-fm*fm)/fz)-fm,
path || fz||'/'||fm||','
from tb where instr(path,','||fz||'/'||fm ||',')=0
)
,tperiodb as (select n, max(length(translate(path, ','||path, ','))-1) len from tb group by n)
select count(*) from (select * from tperioda union all select * from tperiodb) where mod(len,2)=1

  COUNT(*)
----------
      1322

Executed in 23.094 seconds

〇〇

网上找到的快速求质数源代码改造的,比我的oop快30%

loadjava -u LT/LT -v -resolve d:\app\z1.java

create or replace FUNCTION isprimz(x NUMBER) RETURN NUMBER AS LANGUAGE JAVA NAME 'z.getisp(int) return int';
/

create or replace FUNCTION initz(x NUMBER) RETURN NUMBER AS LANGUAGE JAVA NAME 'z.run4(int) return int';
/

我们的存储空间相同，他用int而我用byte
SQL> select 100000000/64+1 from dual;

100000000/64+1
--------------
       1562501

已用时间:  00: 00: 00.01
SQL> select ((100000000+1)/2 / 8 + 2)/4 from dual;

((100000000+1)/2/8+2)/4
-----------------------
             1562500.52

已用时间:  00: 00: 00.01

SQL> select init(100000000) from dual;

INIT(100000000)
---------------
              1

已用时间:  00: 00: 00.97
SQL> select initz(100000000) from dual;

INITZ(100000000)
----------------
       100000000

已用时间:  00: 00: 00.70
SQL> select isprimz(100000000) from dual;

ISPRIMZ(100000000)
------------------
                 0

已用时间:  00: 00: 00.00
SQL> select isprimz(100000000-11) from dual;

ISPRIMZ(100000000-11)
---------------------
                    1

已用时间:  00: 00: 00.01

tree_new_bee

终于整除一套自己能彻底明白的算法了。(word里带的公式编辑器真不错。)

tree_new_bee

实际上上面的算法与111#google到的算法似乎是一样的。

with t0 as (select 23 num from dual)
,t(r, n, a,q,p, path) as (
select 1, num, trunc(sqrt(num)),1, trunc(sqrt(num)), cast(',' as varchar2(4000)) from t0 where trunc(sqrt(num))<>sqrt(num)
union all
select r+1,n,
trunc(q*(sqrt(n)+p)/(n-p*p)), --a'
(n-p*p)/q,  --q'
(n-p*p)/q * trunc(q*(sqrt(n)+p)/(n-p*p)) - p,   -- q'*a'-p
path || p||'/'||q||','
from t where instr(path,','||p||'/'||q ||',')=0
)
select r,n,a,q,p, path, length(translate(path, ','||path, ','))-1 len from t

         R          N          A          Q          P PATH                                                                                    LEN
---------- ---------- ---------- ---------- ---------- -------------------------------------------------------------------------------- ----------
         1         23          4          1          4 ,                                                                                         0
         2         23          1          7          3 ,4/1,                                                                                     1
         3         23          3          2          3 ,4/1,3/7,                                                                                 2
         4         23          1          7          4 ,4/1,3/7,3/2,                                                                             3
         5         23          8          1          4 ,4/1,3/7,3/2,4/7,                                                                         4

[ 本帖最后由 tree_new_bee 于 2011-1-6 19:27 编辑 ]

〇〇

9i的表现真是奇怪：
97#
select min(n),to_char(min(cb)) cb  from tdigis where digis in (select digis from tdigis group by digis having count(*)=5)
                                                                                 *
ERROR 位于第 9 行:
ORA-00600: 内部错误代码，参数: [kkqwrm_noref: COLFDNF set], [], [], [], [], [], [], []

117#
SQL> select initz(100000000) from dual;

INITZ(100000000)
----------------
       100000000

已用时间:  00: 00: 20.08
SQL> select count(l) from(select level l, isprimz(level)i from dual connect by level<=1000000)where i=1;

  COUNT(L)
----------
     78498

已用时间:  00: 00: 11.05
SQL> select init(100000000) from dual;

INIT(100000000)
---------------
              1

已用时间:  00: 00: 09.07
SQL> select count(l) from(select level l, isprimo(level)i from dual connect by level<=1000000)where i=1;

  COUNT(L)
----------
     78498

已用时间:  00: 00: 11.02