1.24

secje posted @ 2010年5月12日 10:31 in sicp , 1255 阅读

用了一段时间的PLT和MIT,就测试数据方面来讲,MIT的效率可以说是龟爬了,开c语言编译都不用这么久,当然了,这是指大数方面

PLT的(current-milliseconds)远远没有MIT的(runtime)稳定,数据差距很大,但是测试多组数据的时候就很好,MIT适合单组数据

因为不知道PLT下面的random是什么,所以就MIT解决了

 

(define (fast-prime? n times)
  (define (expmod base exp m)
    (cond ((= exp 0) 1)
          ((even? exp)
           (remainder (square (expmod base (/ exp 2) m))
                      m))
          (else
           (remainder (* (remainder base m) (expmod base (- exp 1) m))
                    m))))
  (define (fermat-test n)
    (define (try-it a)
      (= (expmod a n n) a))
    (try-it (+ 1 (random (- n 1)))))
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))
(define (start-prime-test n start-time times)
  (if (fast-prime? n times)
      (- (runtime) start-time)))
(define (time-prime-test n times)
  (start-prime-test n (runtime) times))


(time-prime-test 100003 1000)
;Value: .1559999999999917

(time-prime-test 100019 1000)
;Value: .1880000000000024

(time-prime-test 100043 1000)
;Value: .17199999999999704

(time-prime-test 10000000019 1000)
;Value: .3430000000000035

(time-prime-test 10000000033 1000)
;Value: .3269999999999982

(time-prime-test 10000000061 1000)
;Value: .37400000000000944

还是比较接近两倍的,

http://eli.thegreenplace.net/2007/07/09/sicp-section-126/

http://oss.timedia.co.jp/show

这两个都说不是,eli的循环策略很不错,明天可以试试看,放大效果会比较好吧,那个日本人写的测试数据太小了,感觉不靠谱

http://www.cppblog.com/cuigang/archive/2008/03/31/45781.html

http://silvernightsky.ycool.com/post.2239761.html

以上两个是支持两倍的,各种不懂,测试数据大了,MIT就要求debug,具体不清楚

不死心,试了试10^4和10^8

(time-prime-test 10007 1000)
;Value: .125

(time-prime-test 10009 1000)
;Value: .125

(time-prime-test 100000007 1000)
;Value: .25

(time-prime-test 100000037 1000)
;Value: .25
 

这数据让我很无语,真够整的,但是

(time-prime-test 1000033 1000)
;Value: .15600000000000058

(time-prime-test 1000033 1000)
;Value: .17099999999999937

(time-prime-test 1000033 1000)
;Value: .15600000000000236

(time-prime-test 1000033 1000)
;Value: .1559999999999988

(time-prime-test 1000033 1000)
;Value: .15600000000000236

(time-prime-test 1000033 1000)
;Value: .14099999999999824

(time-prime-test 1000 1000)
;Unspecified return value

(time-prime-test 1009 1000)
;Value: .09299999999999997

(time-prime-test 1013 1000)
;Value: .10900000000000176

很明显10^3和10^6就有问题了,基本是1.5倍,这让我对(runtime)的精度很是怀疑,有个办法很好,去找本scheme的书看看,手册之类的,但是scheme的书真的很少,而且英文居多,这本sicp基本让我头大了,虽然立志看原版书,但是没有大牛的英语水平,基本靠着google dictionary过来的

其实我很怀疑eli和那个日本人的测试,理论上来讲,fermat的测试前面是o(log(n)),但是times必须是一定的,可能他们两个的times跟测试数据有关吧,我也不好猜测什么

明天把,先做个循环,看下测试数据,然后联系下eli,问问他是怎么看的,估计又要麻烦裘老师了,恨自己没考上PKU啊,学校差距真的很大,大到提前招的新生都能秒了HDU的大牛队= =

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter