■

日常

学業関係

SCISに2本出した. 論文2は元ネタ読んでから結局20日か. あと, 某会議の発表順も組んだ.
Lyubashevsky and MicciancioのTCC 2008の論文*1はイデアル格子問題ベースの使い捨て署名だった. 鍵サイズ/署名時間/検証時間と全部O~(n). ただ次元を大きめにしなくてはならんという問題があるので実用的ではないと議論されている.

プログラム書いた

魔法分割数 どう書く？org

mapとapplyってやっぱり便利よね.

(use srfi-1)
(use util.combinations)
(define (maho-memo n)
  (define cn (/ (* n (+ (* n n) 1)) 2))
  (define maho-in-memo
    (let1
     tab (make-hash-table 'equal?)
     (define (memo m l v) (hash-table-put! tab (cons m l) v) v)
     (lambda (m l)
       (cond ((= m 0) 1)
             ((hash-table-get tab (cons m l) #f))
             (else
              (memo m l
                    (apply
                     +
                     (map
                      (lambda (a) (maho-in-memo (- m n) (lset-difference equal? l a)))
                      (map
                       (lambda (li) (cons (car l) li))
                       (filter
                        (lambda (li) (= (apply + li) (- cn (car l))))
                        (combinations (cdr l) (- n 1))))))))))))
  (maho-in-memo (* n n) (iota (* n n) 1)))
gosh> ;(time (maho-memo 5))
; real 112.078
; user 107.813
; sys    3.484
3245664

(use srfi-1)
(use util.combinations)
gosh> ;(time (length (filter (lambda (li) (= (apply + li) 65)) (combinations (iota 25 1) 5))))
; real   0.359
; user   0.359
; sys    0.000
1394
gosh> ;(time (length (filter (lambda (li) (= (apply + li) 111)) (combinations (iota 36 1) 6))))
; real  23.313
; user  22.625
; sys    0.578
32134

(1 2 ... 25)から5つ選んだ場合, 1394個の組み合わせが合計して65を満たす. 組み合わせの生成とフィルタ掛けるのにはあんまり時間食ってないから, そこから組み合わせた方が良さそう. 既にソート済みだからそこで枝刈りするのが良いんだろうね.
n=6にすると組み合わせ生成自体で大分重くなってるのでそこから高速化する必要がありそう.

書き直し.

(use srfi-1)
(use util.combinations)

(define (maho-memo n)
  ;tableに足してcnになるリストを入れておく
  (define table 
    (let ((cn (/ (* n (+ (* n n) 1)) 2)))
      (filter
       (lambda (li) (= (apply + li) cn))
       (combinations (iota (* n n) 1) n))))
  (define maho-in-memo
    (let1
     tab (make-hash-table 'equal?)
     (define (memo m l v) (hash-table-put! tab (cons m l) v) v)
     (lambda (m l)
       (cond ((= m 0) 1)
             ((hash-table-get tab (cons m l) #f))
             (else
              (memo m l
                    (apply
                     +
                     (map ; 今のlからaを除いたリストでmaho-in-memoを呼ぶ
                      (lambda (a) (maho-in-memo (- m n) (lset-difference equal? l a)))
                      (filter ;(car l)で始まるtableの中のリストを抜き出す
                       (lambda (li) (and (equal? (car li) (car l)) (lset<= equal? li l)))
                       table)))))))))
  (maho-in-memo (* n n) (iota (* n n) 1)))
;gosh>
;(time (maho-memo 5))
; real  43.391
; user  42.625
; sys    0.641
;3245664

1分切れた.
最大公約数(除算禁止)

ref: http://www.lingr.com/room/doukaku_ja/archives/2007/12/13#msg-20569372
確かにと, 思った. 今からお題に返信つけるのってありっすかね?
投稿に至るまでの気持ち.

  1. フィボナッチ数列で通常のGCDのループ回数の最悪ケースだよね
  2. 大きい整数同士の除算って効率悪いよね
  3. 減算とビットシフトだけで何とかならんか?
    1. お, 出来た. ビットシフトが高速なら割り算使うより速いんちゃう?
    2. ぐぐるとBrentの改良として知られている. 車輪の再発明.
  4. あー, 除算禁止のGCDだと面白いんじゃないかしら?
  5. 10進400桁くらいで回さないと差が見えないだろうな (本当はもっと必要).
  6. じゃぁ多倍長演算サポートで. ついでにフィボナッチ数2つ位出しとけば十分だろう.
  7. 隣り合うフィボナッチ数だと減算オンリーでも速いやorz
  8. 組み込みのGCD使うと思ってなかったorz
  9. 1進表現に直してから正規表現(!)

ref: 最近は見るだけだな : 最大公約数（除算禁止） どう書く？org - λx.x(λx)(tell diary) 2007-12-16
真面目に証明するとそんな感じっすね.
模範解答は#4739です.
Brentの改良自体はR. P. Brent - Twenty years' analysis of the binary Euclidean algorithmというサーベイに纏まっている様子. 流し読みするに細かく解析するのに数学的な道具を沢山使っていて大変そうだなぁという感じ.

*1:Vadim Lyubashevskyにある