From patchwork Sun Jun 20 21:05:58 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Carlini X-Patchwork-Id: 56277 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id AD6131007D4 for ; Mon, 21 Jun 2010 07:06:09 +1000 (EST) Received: (qmail 12374 invoked by alias); 20 Jun 2010 21:06:07 -0000 Received: (qmail 12361 invoked by uid 22791); 20 Jun 2010 21:06:07 -0000 X-SWARE-Spam-Status: No, hits=-1.3 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_NONE, SARE_SUB_RAND_LETTRS4 X-Spam-Check-By: sourceware.org Received: from vsmtp21.tin.it (HELO vsmtp21.tin.it) (212.216.176.109) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sun, 20 Jun 2010 21:06:02 +0000 Received: from [192.168.0.4] (79.52.209.106) by vsmtp21.tin.it (8.5.113) id 4BC86A4905AC2D6F; Sun, 20 Jun 2010 23:05:59 +0200 Message-ID: <4C1E82B6.6010107@oracle.com> Date: Sun, 20 Jun 2010 23:05:58 +0200 From: Paolo Carlini User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.1.9) Gecko/20100317 SUSE/3.0.4-1.1.1 Thunderbird/3.0.4 MIME-Version: 1.0 To: "gcc-patches@gcc.gnu.org" CC: libstdc++ Subject: [v3] Fix uniform_int_distribution for arbitrary urng.max() and urng.min() X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Hi, finally, I returned to this long standing issue, also using as starting point an useful exchange with Kai-Uwe. Tested x86_64-linux, committed. Paolo. //////////////////////// 2010-06-20 Paolo Carlini Kai-Uwe Bux * include/bits/random.tcc (uniform_int_distribution<>::operator()): Fix to work well for arbitrary urng.max() and urng.min(). Index: include/bits/random.tcc =================================================================== --- include/bits/random.tcc (revision 161035) +++ include/bits/random.tcc (working copy) @@ -828,28 +828,62 @@ operator()(_UniformRandomNumberGenerator& __urng, const param_type& __param) { - // XXX Must be fixed to work well for *arbitrary* __urng.max(), - // __urng.min(), __param.b(), __param.a(). Currently works fine only - // in the most common case __urng.max() - __urng.min() >= - // __param.b() - __param.a(), with __urng.max() > __urng.min() >= 0. typedef typename std::make_unsigned::type __urntype; + _UniformRandomNumberGenerator::result_type>::type __urngtype; typedef typename std::make_unsigned::type __utype; - typedef typename std::conditional<(sizeof(__urntype) > sizeof(__utype)), - __urntype, __utype>::type __uctype; + typedef typename std::conditional<(sizeof(__urngtype) + > sizeof(__utype)), + __urngtype, __utype>::type __uctype; - result_type __ret; + const __uctype __urngmin = __urng.min(); + const __uctype __urngmax = __urng.max(); + const __uctype __urngrange = __urngmax - __urngmin; + const __uctype __urange + = __uctype(__param.b()) - __uctype(__param.a()); - const __urntype __urnmin = __urng.min(); - const __urntype __urnmax = __urng.max(); - const __urntype __urnrange = __urnmax - __urnmin; - const __uctype __urange = __param.b() - __param.a(); - const __uctype __udenom = (__urnrange <= __urange - ? 1 : __urnrange / (__urange + 1)); - do - __ret = (__urntype(__urng()) - __urnmin) / __udenom; - while (__ret > __param.b() - __param.a()); + __uctype __ret; + if (__urngrange > __urange) + { + // downscaling + const __uctype __uerange = __urange + 1; // __urange can be zero + const __uctype __scaling = __urngrange / __uerange; + const __uctype __past = __uerange * __scaling; + do + __ret = __uctype(__urng()) - __urngmin; + while (__ret >= __past); + __ret /= __scaling; + } + else if (__urngrange < __urange) + { + // upscaling + /* + Note that every value in [0, urange] + can be written uniquely as + + (urngrange + 1) * high + low + + where + + high in [0, urange / (urngrange + 1)] + + and + + low in [0, urngrange]. + */ + __uctype __tmp; // wraparound control + do + { + const __uctype __uerngrange = __urngrange + 1; + __tmp = (__uerngrange * operator() + (__urng, param_type(0, __urange / __uerngrange))); + __ret = __tmp + (__uctype(__urng()) - __urngmin); + } + while (__ret > __urange || __ret < __tmp); + } + else + __ret = __uctype(__urng()) - __urngmin; + return __ret + __param.a(); }