Computer Chess Club Archives




Subject: Re: Book design

Author: Andreas Herrmann

Date: 11:40:30 11/28/02

Go up one level in this thread

On November 28, 2002 at 13:56:47, David Rasmussen wrote:

>On November 28, 2002 at 05:13:56, Sune Fischer wrote:
>>Can you reveal a few details here :)
>>Binary search, how do I do that?
>Suppose you have an ordered list of integers:
>1  3  4  7  11  19  20 25
>If you're looking for an element in this list, you can search it linearly, from
>beginning to end. For a list of n elements, that takes n comparisons.
>Or you can start in the middle of the list, and check whether that element is
>smaller og larger than the element your looking for. If it is smaller, you do
>this whole thing again recursively on the right, higher part of the list. If
>not, you do it on the left, lower part. This takes log2(n) comparisons. Even if
>you have a million entries, is still only takes 20 comparisons. Of course, if
>you have an old slow disk, this can still hurt, as they are 20 random access
>reads. But on the hardware I have access to, it is not a problem.
>It is not hard to improve this scheme so that much less disk access, but I
>haven't had any reason to improve it yet.

the book of Holmes works in this way. It costs only a few milliseconds to find
the right entry in the book file. So the time should not be the problem, and
this is the normal way to search in sorted data.

My old book has about 109.000 different position entrys and there were a maximum
of 17 comparisons to find the right position. My new book has over 1,7 million
different positions and the maximum of comparisons is here 21.

max.      until n
accesses   entrys
 2              3
 3              7
 4             15
15          32767
16          65535
17         131071
18         262143
19         524287
20        1048575
21        2097151

have a nice day

This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.