From 2b91c8cf007e1008f7d6ccc9813908d30af8b4c0 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Tue, 14 Jun 2005 14:21:43 +0000 Subject: The random selection in function linear() could deliver a value equal to max if geqo_rand() returns exactly 1.0, resulting in failure due to indexing off the end of the pool array. Also, since this is using inexact float math, it seems wise to guard against roundoff error producing values slightly outside the expected range. Per report from bug@zedware.org. --- src/backend/optimizer/geqo/geqo_selection.c | 37 +++++++++++++++++++---------- 1 file changed, 25 insertions(+), 12 deletions(-) diff --git a/src/backend/optimizer/geqo/geqo_selection.c b/src/backend/optimizer/geqo/geqo_selection.c index f956759e7e..c6a635ac95 100644 --- a/src/backend/optimizer/geqo/geqo_selection.c +++ b/src/backend/optimizer/geqo/geqo_selection.c @@ -6,7 +6,7 @@ * Portions Copyright (c) 1996-2001, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $Id: geqo_selection.c,v 1.12 2001/01/24 19:42:57 momjian Exp $ + * $Id: geqo_selection.c,v 1.12.4.1 2005/06/14 14:21:43 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -43,10 +43,11 @@ static int linear(int max, double bias); -/* geqo_selection - * + +/* + * geqo_selection * according to bias described by input parameters, - * second genes are selected from the pool + * first and second genes are selected from the pool */ void geqo_selection(Chromosome *momma, Chromosome *daddy, Pool *pool, double bias) @@ -54,28 +55,27 @@ geqo_selection(Chromosome *momma, Chromosome *daddy, Pool *pool, double bias) int first, second; - first = (int) linear(pool->size, bias); - second = (int) linear(pool->size, bias); + first = linear(pool->size, bias); + second = linear(pool->size, bias); if (pool->size > 1) { while (first == second) - second = (int) linear(pool->size, bias); + second = linear(pool->size, bias); } geqo_copy(momma, &pool->data[first], pool->string_length); geqo_copy(daddy, &pool->data[second], pool->string_length); } -/* linear +/* + * linear * generates random integer between 0 and input max number * using input linear bias * * probability distribution function is: f(x) = bias - 2(bias - 1)x * bias = (prob of first rule) / (prob of middle rule) - * */ - static int linear(int pool_size, double bias) /* bias is y-intercept of linear * distribution */ @@ -83,8 +83,21 @@ linear(int pool_size, double bias) /* bias is y-intercept of linear double index; /* index between 0 and pop_size */ double max = (double) pool_size; - index = max * (bias - sqrt((bias * bias) - 4.0 * (bias - 1.0) * geqo_rand())) - / 2.0 / (bias - 1.0); + /* + * If geqo_rand() returns exactly 1.0 then we will get exactly max from + * this equation, whereas we need 0 <= index < max. Also it seems possible + * that roundoff error might deliver values slightly outside the range; + * in particular avoid passing a value slightly less than 0 to sqrt(). + * If we get a bad value just try again. + */ + do { + double sqrtval; + + sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(); + if (sqrtval > 0.0) + sqrtval = sqrt(sqrtval); + index = max * (bias - sqrtval) / 2.0 / (bias - 1.0); + } while (index < 0.0 || index >= max); return (int) index; } -- cgit v1.2.1