Presentation	2010-03-04 New Implementation and Evaluation of Knuth-Yao Algorithm and the Interval Algorithm Shogo TAKAHASHI, Hirosuke YAMAMOTO,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	In this paper, new implementation algorithms are proposed for Knuth-Yao algorithm and the Interval algorithm, which can generate a sequence with an arbitrarily given discrete probability P_ from a binary random sequences {X_i}. The proposed algorithms don't require high precision in operation and can achieve P_ without error. For the Interval algorithm, we derive the exact theoretical value of the average bit length E[L] of X_i necessary to generate one symbol of Y for |y|=2 and 3, where |y| is the cardinality of alphabet of Y. Furthermore, a new tight upper bound of E[L] is derived for |y|≧4.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	Knuth-Yao algorithm / interval algorithm / random number generation
Paper #	IT2009-89,ISEC2009-97,WBS2009-68
Date of Issue

Conference Information
Committee	ISEC
Conference Date	2010/2/25(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Information Security (ISEC)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	New Implementation and Evaluation of Knuth-Yao Algorithm and the Interval Algorithm
Sub Title (in English)
Keyword(1)	Knuth-Yao algorithm
Keyword(2)	interval algorithm
Keyword(3)	random number generation
1st Author's Name	Shogo TAKAHASHI
1st Author's Affiliation	Graduate School of Frontier Sciences, The University of Tokyko()
2nd Author's Name	Hirosuke YAMAMOTO
2nd Author's Affiliation	Graduate School of Frontier Sciences, The University of Tokyko
Date	2010-03-04
Paper #	IT2009-89,ISEC2009-97,WBS2009-68
Volume (vol)	vol.109
Number (no)	445
Page	pp.pp.-
#Pages	6
Date of Issue