From owner-svn-src-all@freebsd.org Tue May 31 13:25:32 2016 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 7FA34B559FA for ; Tue, 31 May 2016 13:25:32 +0000 (UTC) (envelope-from mailing-machine@vniz.net) Received: from mail-lf0-f54.google.com (mail-lf0-f54.google.com [209.85.215.54]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 1127D1BCC for ; Tue, 31 May 2016 13:25:31 +0000 (UTC) (envelope-from mailing-machine@vniz.net) Received: by mail-lf0-f54.google.com with SMTP id b73so67807595lfb.3 for ; Tue, 31 May 2016 06:25:31 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:subject:to:references:cc:from:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding; bh=m2iDKW35cnqo8f1HhqVWr1epwLt5isAaJvw/OoGJ3bU=; b=bD7mWElOlKTZ/uifnigjrO+wO5gPWLOqIT27yGhOY1gzwdow0pSAaO5GnO88Ni0QzY Br/IqhniEaL3LmQNFEPuRdRkCS6djqC6scmY1pCHkvZBaoDouraMQSNNzTFroNQHIlN+ yoMfcMzVn7CipLDCxb7X2AY8Web6pM5Kdxmk87E643VeYhMT8SzcL3qwIJ8HTm7vWhEa XWhT6AwOCHzI/dmi8jO5WhOAPMvFF57JPNiI9SEOu1XL0v/K8dp4zTjlS5Q1h9pb2vUw IUptsZswXIPSK0hkfyx5hDFTOc+WQST5hww3pIBoZHRpUqZDVyShKUCytuuHoPu4l8Oj n1Tw== X-Gm-Message-State: ALyK8tLuNjmxF7qG5FH5ESGjmIRYaZtaqqR2w73c4JhEdk88grskoJdZ/XWsMV8k5AeyVg== X-Received: by 10.46.71.213 with SMTP id u204mr7752844lja.15.1464701124424; Tue, 31 May 2016 06:25:24 -0700 (PDT) Received: from [192.168.1.2] ([89.169.173.68]) by smtp.gmail.com with ESMTPSA id u188sm2654669lja.11.2016.05.31.06.25.23 (version=TLSv1/SSLv3 cipher=OTHER); Tue, 31 May 2016 06:25:23 -0700 (PDT) Subject: Re: svn commit: r300956 - head/lib/libc/stdlib To: Bruce Evans References: <201605291357.u4TDv6No071840@repo.freebsd.org> <20160530110541.I924@besplex.bde.org> <20160531155327.I1534@besplex.bde.org> <20160531185907.Y2047@besplex.bde.org> Cc: pfg@freebsd.org, src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org From: Andrey Chernov Message-ID: <92189e8c-8434-9b54-acf9-9909e647a0db@freebsd.org> Date: Tue, 31 May 2016 16:25:22 +0300 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.1.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.22 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 31 May 2016 13:25:32 -0000 This implementation of shifts&xors 32-bit and 64-bit PRNGs looks more reliable than Mersenne primes and don't use Bignums: http://wwwmaths.anu.edu.au/~brent/ftp/random/xorgens305.tar.gz PDF article inside. On 31.05.2016 14:30, Andrey Chernov wrote: > On 31.05.2016 12:58, Bruce Evans wrote: >> On Tue, 31 May 2016, Andrey Chernov wrote: >> >>> On 31.05.2016 9:48, Bruce Evans wrote: >>>>> Perhaps you can find some ideas, answers and PRNG comparison in the >>>>> original paper: >>>>> http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf >>>> >>>> The ones with Mersenne primes and tweaked Mersenne primes in the >>>> reference >>>> (lanl?) given by pfg@ seem OK. >>> >>> It should be again correctly implemented to not overflow 64bit (as any >>> other 64bit generator too). >>> >>> Moreover, it have visible patterns in the low order bits. This one from >>> the same site is better >>> http://nuclear.llnl.gov/CNP/rng/rngman/node7.html >>> but still have some pattern too and 61-bit. Next one does not suffer >>> from the pattern at all >>> http://nuclear.llnl.gov/CNP/rng/rngman/node8.html >>> but is 2^64-2^10+1. >> >> That's the tweaked Mersenne prime one. >> >> Surely there is a pattern in the bits for all of these, and the better >> ones just hide the pattern better from normal uses and tests? > > Excepting bad first one from pfg@ > http://nuclear.llnl.gov/CNP/rng/rngman/node4.html > as I understand, they not hide (i.e. drop) the pattern but mix it with > other part in calculations, it cause whole range reduced. > >>> You can download SPRNG library implementing all of them here: >>> http://www.sprng.org/RNG/ >>> For me it is overcomplicated. >> >> The general case is certainly too complicated. It would let the user >> specify all the parameters for the LCG and generate optimal code for >> the choice on the fly. Maybe also change the parameters with the seed. >> But even most implementors don't know how to choose the parameters. >> That's just for the not so good LCG family of RNGs. > > All mentioned PRNGs with exact parameters (info.h) can be found in the > subdirs under SRC, f.e. lcg64 or pmlcfg. They are still looks > complicated and use GMP Bignum library for calculations.