Journal Article / 学術雑誌論文 Construction of a nonrecursive 64-bit pseudorandom number generator based on beta transformations on [1,2) [1,2)上のベータ変換に基づく非再帰型64ビット擬似乱数 の構成 YAGUCHI, Hirotake 谷口, 礼偉 三重大学教育学部研究紀要, 自然科学・人文科学・社会科学・教育科 学. 2014, 65, p. 19-25. http://hdl.handle.net/10076/13947 三重大学教育学部研究紀要 第 65巻 自然科学 (2014) 19- 25頁 Cons t r uc t i onofanonr e c ur s i ve64bi t ps e udor andom numbe rge ne r at orbas e donbe t a t r ans f or mat i onson[ 1, 2) Hi rot akeYAGUCHI* [1, 2)上のベータ変換に基づく非再帰型 64ビット擬似乱数の構成 谷 口 礼 ― 19― 偉 谷 口 礼 偉 1 nt h en e x ts e c t i o nweg i v ea l g o r i 也 ma 且 di m p l e m e n t a t i o no f8 8 1 6 4 r 乱n d, and 岨 db ya p p l y i n gN18T'ss u i t eo ft e s t i n g i n3 3t e s tt h erandomnesso f8 8 1 6 4 r randomne 呂田 [ 7 ]andT e s tU 0 1byL'Ecuyer[ 1 ] . 3 2 .AlgorithmandimplementationofSSI64r 岨 d . AIgorithmofSSI64rand. L e t, Mβ : [ 1, 2 )→ [ 1, 2 )beab e t at r a n s f o r 2 .1 2 )d e f i n e dby~β (t) = βt一日り+1 ,β >1,wherel s t Ji st h e mationon[ 1, 前 i n t e g e rno 七e x c e e d i n gs t .(Weoftenadopttheno凶 ionappear吋 i n[ 6 ] . ) l a r g e L e t1 .eand1宵benumbersde 五n edby1 .2 7 1 8 1・ ・ ・ a 且 d1 .3 1 4 1 5・ ・ ・ r e s p 巴 c t i v e l y 巴m a t i c a lc o n (Then o t a t i o neandπimpliesN a p i e r ' sc o n s t a n tandt h emath s t a n tp ir e s p e c t i v e l y . )We自r s tu s e1 .e .L e tt h eb i n a r yr e p r e s e n t a t i o no f1 .ebe 1.九九... 1 ' 63・ ・ ・ .F o rag i v e nn o n n e g a t i v e6 3 b i ti n t e g e rV1V2・ ・ ・ V63 wem ake乱 numberxi n[ 1, 2 )from1 .eby x= ・ ・ 1 . ( 1 '1E 9V1)(ゐ⑦ V2)・ ・ ・( 1 ' 63E 9v63)' 1 1 64' 65・ , ( 1 ) whereE 9i st h el o g i c a lo p e r a t i o nXOR( e x c l u s i v eo r ) . Wew r i t e( 1 )s u c l 1ω x =( 1 .e)E 9(V1V2'" V63)f o rs h o r t .L e t即日 beaf i x e dnumberi n[ 1, 2 ) .Thenw巴 compute u=Mgz( 旬 。 )= L I i7 b 8・ ・ ・ b127b128・ ・ ・ ( i nb i n a r y ) . ( 2 ) I fweputωo=x andt a k eo u tb32b33・..b95ω a6 4 ヶb 比r andomnumberfromu, 出 sa l g o r i もhmi sもhesamea sMB32randi n[ 6 ]exωptf o r七heb比 由e .However i n8 8 1 6 4 r a n d, i no r d e rt oi n c r e a s erandomness, wef u r t h e rcompute y= ( 1 : 1 l ' )E 9(V1V2'・ ・ V63) 阻 d v三 ・ ・ Mgu(60)=18788・ ・ ・ b127b128・ e c t i v e l y . f o rWoandV1V2...V63whi c l 1町 ed i f f e r e n tfromωoandV1V2・ .V63r e 呂 町p i n a r ys et h er e s u l to fb u b t r a c t i o nlb7b8・ L e tbob7b8 ・ ・ b127b ・ b127ー lb7b8 ・ ・ b127・ e q u e n c e Thenas乱 6 4 -b i trandomnumber(wet a k eo u tb32b33・ akeas ・ ・ b95・Tom o frandomnumbers{ w e u s e ( k} , . 1 , 2 k=0, ( O x 3 9 f 7 5 0 2 4 1 c 2 d 5 d 3 3 )xk mod Ox 7fffffffffffffe7, ( 3 ) ( O x 3 2 f 5 0 f e e 9 b 2 a 3 2 b b )xk mod Ox7fffffffffffff5b ( 4 ) 吋 , d ノ e s p e c t i v e l y .( ・ V63a 低 : x a 舵 a st h ek -t hV1V2・ ndV1V2 ・ f e c O xmeans" i nt h eh e : ' 6 3r 凶 伽 閃 e p 田 印 叩 阻 r戸r e nt a o n nM iX( U t 抗 副 七 “i 町 ぜ " つ ' . ) 8ox dUi J 2 P 乙 加 i m叫 ο(1.♂巴吋)E9伊 V1V' ( 2 " : Xk= 均 6 3 心 ) 乱nd 'Vj 均 y . ο(1.71'宵吋)E9( v ) 仇 I I t 1 ' ' 6 3 ) ら : V 九 ' 2 '. 仇k = r e s p e c t i v e l y . (Ofc 4 )悶 primen o u r s ea l li n t e g e r si n( 3 )副 ( u m b e r s ;ands o 1 2 6 8. p p r o x i m a t e l y2 同 1 e r i o do 岨 di sa 03 )Numbersωoand向 m t h ep f8 8 1 6 4 r a n g eas e q u e n c eo f8 8 1 6 4randomn u m b e r s . Ast h ei n i t i a lv a l u e swe u s e d七oc l 1 .e阻 dwo=1 .宵 . u s eWo= 1 2 . 2 .ImplementationofSSI64rand.Weimplementt h ea l g o r i t h mo f8 8 1 6 4 o l l o w i n g6 y s 旬m r a n di nt h ef 4 -b i tnumbers : ― 20― Nonr e c ur s i ve6 4bi tps e udor andom numbe rge ne r at or 1 )anumb 巴rl .b b . . b n[ 1, 2 )i sroundedt o6 4 b i tl .b b . .b ・ ・ i 1 2. 6 3b 6 4・ 1 2. 6 3, 2 )am u l t i p l i c a t i o no f6 4 -b i tnumbersl . tl t 2・ ・ ・t 6 3乱 凶 l .x l x 2. . . X 6 3i s p e r f o r m e dp r e c i s e l yandy i e l d sa1 2 8 b i tnumberb b . b b . . b o 1 2 3. 1 2 7 w i t hb b 1o rb e p e n d i n gonwhethert h er e s u l ti si n[ 1, 2 )o r o 1= 0 o= 1d [ 2, 4 )r e s p e c t i v e l y , 3 )a6 4 b i tnumberl .b 62i st a k e no u tfromar e s u l tb b ・ ・ .b ゐb sb s+ 1 S+ 1 o 3・.. b o f m u l t i p l i c a t i o n . ( 8 d e p e n d s o n c o n t e x t a n d 8 = 7 f o r M 5 ( t ) ) 1 2 7 2 . 1 ti sc o n v e n i e n tf o ru呂志oi d e n t i そ ya6 4 -b i tnumberl .b b . .b 2 8 b i 色 1 2. 6 3阻 d乱 1 numberb b 2 3 ・ ・ b w i t h i n t e g e r s l b b . . . b 叩 d b b b b ・ ・ b r 偲 p e c b o1 1 2 7 12 6 3 o123 1 2 7 → Numbersl .e岨 dl : r ra r ei d e n t i f i e dw i t h t i v e l y .Hencebelowwedoi t .( " , ι Oxa2cb4411ba257552 乱nd Oxa8365eed3gelc070 r e s p e c t i v e l y . )8 i n c eM25 " , ( t )i sc a l c u l a t e ds u c ha s M2 5. , ( t ) = ( 25 x ) tmod[ 1, 2 ) =( 25 ) ( x t )mod[ 1, 2 ) ・ ・ mod[ 25X8081. 8 2 8 3る b b b 2 ) 1, 5 6 7 S 4 'b b 2 ) 1, " mod[ b o b l b 2 b 3 b 4 b 5 b 6.b 7 s' 1.b 7b s・・・, 同 i o no fM 25 ( -b i ti n t e g e rs y s t e mi sp e r f o r m e ds acompu t )underour64 u c ha s " , ・ ・X 1 X I X 2・ 6 3 ・t l t l t 2・ 6 3 muj ー ー → ~ b b b b b o 1 2・ 5 6 7・・・・・・ 8 ・ ・b 1 2 7 l b7・ ・ ・b ・ ・8 1 2 7 6 9・ 6 竺 立 8 b b 6 9・ 1 2 7 6 7・ ・ ・b ・ ・b 2L 18788・ ・ ・b 6 9・ M i t .. 岨 e d e n 8uppose b r ei b )阻 dMJPh(1π)a dwi 七hl b 7 b S・ 7 s・ n( 1 .e ・ ・b 1 2 7乱 凶 1 日 七b e s p e 氾 七i v e l y .Then h8 8 1 6 4randomnumber( st h e64b i b -t ni ・ ・b 1 2 7r 3 2b 3 3・ 9 5 . . . . . . . 古 i nb w h i c h i s h e r e s u l も o f b i n a r y s u b t r a c t i o n l b l b b b b b b b o7s 1 2 7 7s・ 1 2 7 7s . 阻 l p l e七hef i r s tandt h es e c o n d8 8 1 6 4randomnumbers乱r e O x 8 e α αfb19 b .Forex 1 27 e s p e c t i v e l y .1 p p e n d i xweg f73587f8andO x 4 b b 2 5 3 3b46fb 5cflr i v eac o d e nt h ea 岨 d omnumb巴r . o fcomputingan8 8 1 6 4r ~3. ndomnessofSSI64r Ra 四 d 且d omnumbersg e n e r a t e dby8 8 1 6 4 r a n dby Wet e s t e dt h erandomnesso fr a a p p l y i n gN18T'ss t s 2 .1 内 B t a t i s t i c a lt e s ts u i t es .1[ igCrushs u i t e 7 ]andL'Ecuye r e p e a 1 8 T ' s ' 1 1 回 i n U01V.1 .2 . 3[ susua . l We 七e dN 七e s 七s u i t e1 0t i m e sf o r 1 ]a c o n s e c u t i v e1 i l e sc o n s i s t i n go foneg i g a b i t s田 d色ooka v e r a g eo f1 e s u l t so f 0f 0r 五e l o c kl e n g t hも0 e s t .( 1 nt h eb l o c kf r e q u e n c yt 2 0 0 0 0 . ) d出 eb e a c ht e sもwemodi 巴 呂 町ea Themaximum乱ndt h eminimumo ft h ea v e r a g e dv a l u sf o l l o w s : ― 21― 谷 口 礼 偉 [ 8 8 1 6 4 r 阻 d ] P-VALUEAvMax= 0 . 7 4 2 5 1 7a tNonOverlappingTemplateド=1 3 1 ] P-VALUEAvMin= 0 . 1 8 5 7 0 3a tNonOverlappingTemplate[ i= 4 5 ] PROPORTIONAvMax= 0 . 9 9 2 7 1 9a tR皿 domExcUIsionsVariant[ i= 1 7 9 ] tRan domExcursions[ i= 1 5 9 ] PROPORTIONAvMin= 0部 6145a p -v a l u e swhiche a c ht e s to ft h es u i t eg e n e r a t e 呂 町ee x p e c t e d I nt h er e s u l tabove, 1 ] . PROPORTION(FRACTION)i st h ep r o p o r t i o n t os p r e a du n i f o r m l yi n[ 0, h et e s ta tt h el e v e lo f0 . 01 . (Thei o fs e q u e n c e so frandomnumberswhichp剖 st i n[ i= x ]i st h es e r i a lnumbero ft h et e 凶 i n七hes u i 七e . )Below, f o rc o m p a r i s O I 巾 s a k e, wec i t e出 er e s u l 七o fMersenneT w i s t e r紅 pseudorandomnumberg e n e r a t o r [ 8 ] [ 6 ] : [ M e r s e n n eT w i s t e ra r ] P-VALUEAvMax= 0 . 7 1 3 5 7 8a tNo 凶 v e r l a p p i n g T e m p l 抗 eド=1 0 5 ] P-VALUEAvMin= 0 . 1 8 8 7 4 5a tNonOverl 乱p pin gT emplate[ i= 1 2 6 ] PROPORTIONAvMax= 0 . 9 9 2 8 7 9a t加 do mE x c u r s i o n s V a r i a n t[ i= 1 6 8 ] PROPORTIONAvMin= 0 . 9 8 6 8 0 9a tRa ndomExcUIsions[ i= 1 5 9 ] 色wea p p l i e dBigCrusho fTes 七U0 1 .I nTestUOle a c h七e s tr e q u i r e s3 2 -b i も Nex i n t e g e r so rd o u b l ep r e c i s i o nnumbersi n[ 0, 1 ] .When乱 d o u b l ep r e c i s i o nnumber i n[ 0, 1 ]wasr e q u e s t e d, wef i r s tmadeanumberi n[ 1, 2 )byp u t t i n gt h ef i r s t5 2b i t s 0 ki nt h em阻 t i s s aands e t t i n gi t sexponentt obe. . .x2, 岨dthens u b t r a c t o f( one企omt h enumber. Whena3 2 b i tnumberw錨 r e q u e s t e dwes u p p l i e dt h e f i r s th a l fandthent h es e c o n dh a l fo f( k .Thet e s t sc o n s i s t i n go fBigCrushwere ,andtheresultofBigCrushw,掛 "Alltestswerepωsed". e x e c u t e dp a r a l l e l l y The色imer e q u i r e df o rBigCrushwasabou 色2 50h o u r son(X 凹 n3 . 1GHz)+ (Windows7P r o f e 副o n a l6 4 -b比 ) . (TesもUOlallowsonly3 2 b i tg c c, 佃ds owe canno 七u s et h e6 4 b i tcodei nt h eappendix, whichi sabout7t i m e sf a s t e rthan au s u a l3 2 b i tC c o d e . ) 叫 i onofSSI64randomnumbers Remark.Distrib E s s e n t i a l l yabeta仕 組s f o r m a t i o nMβ ( 8 )=β8-l s 8 J+1on[ 1, 2 )i sas p e c i a l v e r s i o no fl i n e 乱rm odonet r 岨 s f o r m a t i o nTs, α:[ 0, 1 )→ [ 0, 1 )d e f i n e dby 勾ρ ( x ) = βx+αmod1 = βx+日 ー しsx+αJ (0三αく 1 ) MβandTs, α 町 er e l a t e ds u c h国 [ 2 ][ 3 ] .I nf a c t, Mβ ( t )=, Tβ,,a( t-1 )+1 ,tε[1, 2 ), ( 5 ) ,n ; : > : O, - Z〈 T F z α( 1 ) ― 22― P エネ 刈 hs, , .( x )= Z 一 - c t i o n a lp紅 tofβ)[ 6 ] .80wec 阻 m akeu s eo fr e s u l t s whereβ=β-lsJ(=也 eをa o fr e s e a r c h e saboutl i n e a rmodon 巴 仕 組s f o r m a t i o n, Tβ , α・ E s p e c i a l l yw巴 know t h a t ( 6 ) Nonr e c ur s i ve6 4bi tps e udor andom numbe rge ne r at or d e f i n 白 血 i n v 副 阻tm 巴 制r 巴V s, α( E )= J E h s, α( x ) d λ( x )f o rT s , . a , whereT ! J , a .( l ) = l i m 1+0T! J , a .( x )and入 i sLebe 昭 l emeωureon[ 0, 1 )[ 2 ] [ 3 ] . Fr omt h i swe h a v e ",→ 一日 + く 一 z く 一 hμ n 一 円 ( 7 ) 6)乱 ( 呂 田 [ 6 ] ) .I n凹 rS S I 6 4 r a n dtheβisi n[ 25, 2 ,ndso占<品三占 Also 舗 u r e μ β, αofvs, αweh a v e c o n c e r n i n gt h en o r m a l i z e dme • ん1)f(U)仰 N-I • J ! 弘元呂問 α( x ) )= α( y )a . a .x . ( 8 ) F r omt h e s 巴 c i r c u m s t a n c e swet h i n kt h a twec 乱np r o v et h a ti fki s1 乱r g e, t h e n x )undert h ea s s u m p t i o nt h a txs p r e a d su n i おr mlyi n t h ed i s t r i b u t i o no fM. ( 2 )i sa p p r o x i m a t e dbyt h en o r r r 叫 i z e dme 回 u r eon[ 1, 2 )d e r i v e dfrom [ 1, ι r2 H()=Lh{EEZ7( 胸 [ 4 ] [ 6 ] . References [ 1 ]P .L ' E c u y e r乱ndR .Simard, ' D 田t U 0 1 :A C L i b r a r yf o re m p i r i c a lt e s t i n go f 叩 domn umberg e n e r a t o r s, ACMT r a n s αc t i o n sonM a t h e m a t i c a l8 0 } 加品問 r vo l .3 3, n o .4( 2 0 0 7 ), A吋 i c l e2 2 . 七p : jjwww. i r o . u m o n t r e a l . c a j“sim 紅 d r j 闘 t u 0 1 j 同0 1 .h 七m l ) ( h , Re p r e s e n t a t i o n sf o rr e a lnumbers, A c t aM a t h .A c a d .8 c i .H u n g a r ., [ 2 ] W.P a r r y vo l .1 5( 1 9 6 4 ), p p .9 5 1 0 5 . .M.W i l k i n s o n, E r g o d i cp r o p e 凶i e so fc e r t a i nl i n e a rmod0配 t r a n s f o r m a [ 3 ]K t i o n s, A d v a n c e si nM a t h ., vo l .1 4( 1 9 7 4 ), p p .6 4 -7 2 . I iand1 .Kubo, Anewn o n r e c u r s i v epseudorandomnumberg e n e r [ 4 ]H .Y a g u c l 飢o rb舗 巴donc h a o smappings, MonteC a r l oMethodsA p p l ., vo l .1 4( 2 0 0 8 ), p p .8 5 9 8 .DOI10.1515jMCMA.2008.005 [ 5 ]H .Y a g u c l Ii阻dS .Ued , 乱 Cons七ruction,randomnessandsecurityofnew hashf u n c t i o n sd e r i v e dfromc h a o smappings, l n t e r d i s c i p l i n αr yl n f o 門n a t i o n 8c 問問問 v o l .1 8n o .1( 2 0 1 2 ), p p .1 11 .DOI1 0剖 3 6 j i i s . 2 0 1 2 . 1 [ 伊 阿 句 6 ]H 王 Y姥 a g 思 噌u 吋 1 ons t r 佃 a n 邸s お 伽 r 皿a 剖凶 . 色 t i o 凶 o n件 [ 1 ス 劫 ) . Iηhttp:jj c s r c . n i s t伊 vjgroupsjSTj t o o l k i t j r n g j i n d e x . h t m l ― 23― 谷 口 礼 偉 [ 8 ] http://www.math.sci .hiroshima u.ac.jp;-m-matjMTjMT2002jmt19937 紅 .html Appendix. Herewegiveacodeofgenera 七ing乱n 88164ra 且 domnumber. The ∞dewastω古edby1nぬl'sicl(64-b比)叩d g∞(64-bi古). Thewhole88164randis 皿 a thl.edu.mi e -u.ac.jpjyaguchij88164r阻 d. l 山nl. athttp:// //ホホ**事事車場事ホホ*柿本車場事ホホ*本事様車場事ホホ*旗本 #defineMB_W64_X64_16( o u . 七 , i n l, i n 2 )¥ ー_ asm_ ー( " m o v%3,. Y Y . rc x ; ¥ mov%2,. Y Y .r田; ¥ mov $Ox8000000000000000,Y . % rl 0 ;¥ ' y ' rl0,Y . Y . r 田; ¥ or y mul Y . Y . r c x ; ¥ sh1 $6,. Y Y . r d x ; ¥ . Y . r 田; ¥ shr $58,Y ' y ' rdx,% Y . r 田; ¥ or y l labove 1 repeat from " o r " 乞o I l o r 4乞i m e s or Y . Y . rlO,Y . Y . r 田; ¥ mul Y . Y . rc 玄 ; ¥ Y Xr 也 J % 0 ; mov. ¥ ' y ' ra . x , % 1 ; movy ¥ ¥ " " = r "( o u ' 乞. h i 6 4 ),"=r"{。凶 . 1 0 6 4 )¥ " r "【i n l )," r "【i n 2 )¥ " % r 日ヘ "Xrcx"J " Y . r d . x " , " Y . rl0" ¥ //申**啄*事事事事申**旗本事事事事***旗本事事事事***旗本 #defi 田 SUB_128_128_SHL32(out,inl,i n 2 )¥ Y Y .r田; ¥ __asm__( " m o v% 2 .. mov%3,Y . Y . r d x ; ¥ . X rcx; ¥ mov%5,Y ' y ' rcx,% y ' r d x j¥ suby . X rcx; ¥ mov%4,Y ' y ' rcx,y . y . r 田; ¥ sbby movY . Y . rdx,Y . Y . r c x ;¥ sh1 $32,. Y %r 田; ¥ shr $32,Y . % r c x ; ¥ . Y . rcx,Y . Y . r 田; ¥ or Y shl $32,. Y % r d x ; ¥ . Y . r田 J . Y O ; ¥ movY ' y ' rdx,% 1 ; ¥ movy " ¥ " = r "( o u t. h i 6 4 ),"=r"(。凶 . 1 0 6 4 )¥ ' r ! !( i n1 .1 0 6 4 )J" r "( i n 2. h i 6 4 ),I I r "( i n 2. 1 0 6 4 )¥ " r "【inl.hi64)J I " Y . r 日ヘ"Y. r c x "J " Y . r d . x "¥ ); //申**啄*事事事事申**旗本事事事事***旗本事事車事***旗本 typedef struct f ― 24― Nonr e c ur s i ve6 4bi tps e udor andom numbe rge ne r at or unsigned long long i n " 七 1 064; 七 h i64; unsigned 10ng 10ng i n ' } my_i12 8 ; //榊材料帥柿肺機事事事申柿肺機事事事事事材料本市// U且 signedlong long int genSSI64rand(unsigned long long int x, unsigned long long int t, unsigned long long int y, unsigned 10ng 10ng int s ) f my_i128 u,v,umv; MB_W64_X64_16(u,t,x); MB_W64_X64_16(v,s,y); SUB_128_128_SHL32(umv,u,v); return【umv.hi64); } //材料材料帥柿材料帥材料材料帥柿榊 ― 25―
© Copyright 2023