math_normal.go

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE-go file.

package rand

import (
	"math"
)

/*
 * Normal distribution
 *
 * See "The Ziggurat Method for Generating Random Variables"
 * (Marsaglia & Tsang, 2000)
 * http://www.jstatsoft.org/v05/i08/paper [pdf]
 *
 * Fixed correlation and increased number of distinct results generated,
 * see https://github.com/flyingmutant/rand/issues/3
 */

const (
	rn = 3.6541528853610088
)

func absInt64(i int64) uint64 {
	if i < 0 {
		return uint64(-i)
	}
	return uint64(i)
}

// NormFloat64 returns a normally distributed float64 in
// the range -math.MaxFloat64 through +math.MaxFloat64 inclusive,
// with standard normal distribution (mean = 0, stddev = 1).
// To produce a different normal distribution, callers can
// adjust the output using:
//
//  sample = NormFloat64() * desiredStdDev + desiredMean
//
func (r *Rand) NormFloat64() float64 {
	for {
		v := r.Uint64()
		j := int64(v) >> 11 // Possibly negative
		i := v & 0xFF
		x := float64(j) * wn[i]
		if absInt64(j) < kn[i] {
			// This case should be hit better than 99% of the time.
			return x
		}

		if i == 0 {
			// This extra work is only required for the base strip.
			for {
				x = -math.Log(r.Float64()) * (1.0 / rn)
				y := -math.Log(r.Float64())
				if y+y >= x*x {
					break
				}
			}
			if j > 0 {
				return rn + x
			}
			return -rn - x
		}
		if fn[i]+r.Float64()*(fn[i-1]-fn[i]) < math.Exp(-.5*x*x) {
			return x
		}
	}
}

var kn = [256]uint64{
	0xef33d8025bc39, 0x0, 0xc08be98f2acaa, 0xda354faba4236,
	0xe51f67ec049b5, 0xeb255e9d2fa41, 0xeef4b817e221c, 0xf19470af9cc80,
	0xf37ed61ff712f, 0xf4f469560df95, 0xf61a5e41b6be3, 0xf707a75536926,
	0xf7cb2ec281ec3, 0xf86f10c6337d8, 0xf8fa657830a7d, 0xf9724c74db926,
	0xf9da907dbe051, 0xfa360f581e82e, 0xfa86fde5b3bbf, 0xfacf160d34659,
	0xfb0fb6718ac00, 0xfb49f8d5368f8, 0xfb7ec2366f3be, 0xfbaece9a1db40,
	0xfbdab9d0402f4, 0xfc03060ff6416, 0xfc28210379aaa, 0xfc4a67ae254c3,
	0xfc6a2977ae7a2, 0xfc87aa928908b, 0xfca325e4bd8d3, 0xfcbcce9021dc6,
	0xfcd4d12f834c6, 0xfceb54d8fe7e8, 0xfd007bf1dc4c6, 0xfd1464dd6c0ba,
	0xfd272a8e2f060, 0xfd38e4ff0c565, 0xfd49a9990b0f2, 0xfd598b8920bf9,
	0xfd689c08e96bd, 0xfd76ea9c8e52a, 0xfd848547b0606, 0xfd9178bad29cc,
	0xfd9dd07a7ab32, 0xfda9970105c08, 0xfdb4d5dc02bb8, 0xfdbf95c5bfa83,
	0xfdc9debb99848, 0xfdd3b8118707e, 0xfddd288342d86, 0xfde6364369d6f,
	0xfdeee708d4f6d, 0xfdf7401a6b25d, 0xfdff46599eb80, 0xfe06fe4bc2343,
	0xfe0e6c225a0b8, 0xfe1593c28b6ba, 0xfe1c78cbc3e15, 0xfe231e9db1b32,
	0xfe29885da1a27, 0xfe2fb8fb54027, 0xfe35b33558bf6, 0xfe3b799cffee1,
	0xfe410e99eac3f, 0xfe46746d475ff, 0xfe4bad34c082f, 0xfe50baed29401,
	0xfe559f74ebb5b, 0xfe5a5c8e410ff, 0xfe5ef3e13857d, 0xfe6366fd90f75,
	0xfe67b75c6d47c, 0xfe6be661e10b4, 0xfe6ff55e5f402, 0xfe73e5900a617,
	0xfe77b823e9d56, 0xfe7b6e3706fc3, 0xfe7f08d77416b, 0xfe8289053efb9,
	0xfe85efb35166d, 0xfe893dc84079b, 0xfe8c741f0cdf8, 0xfe8f9387d4e36,
	0xfe929cc879a62, 0xfe95909d38833, 0xfe986fb9399ee, 0xfe9b3ac7147b7,
	0xfe9df2694b62a, 0xfea0973abe5d4, 0xfea329cf16600, 0xfea5aab32948c,
	0xfea81a6d5737c, 0xfeaa797de1c56, 0xfeacc85f3d889, 0xfeaf07865e5a9,
	0xfeb13762feb82, 0xfeb3585fe29bd, 0xfeb56ae316229, 0xfeb76f4e28471,
	0xfeb965fe61f8d, 0xfebb4f4cf9cf9, 0xfebd2b8f4494f, 0xfebefb16e2dbf,
	0xfec0be31ebd6c, 0xfec2752b1599a, 0xfec42049daf5b, 0xfec5bfd29f121,
	0xfec75406cee81, 0xfec8dd2500c42, 0xfeca5b6911ea1, 0xfecbcf0c42790,
	0xfecd38454faa9, 0xfece97488c84a, 0xfecfec47f914f, 0xfed13773584c1,
	0xfed278f84489e, 0xfed3b10242ee8, 0xfed4dfbad580c, 0xfed605498c37d,
	0xfed721d414f89, 0xfed8357e4a924, 0xfed9406a42c6d, 0xfeda42b85b6a9,
	0xfedb3c8746a5a, 0xfedc2df4165fa, 0xfedd171a46dfb, 0xfeddf813c8a7d,
	0xfeded0f90992c, 0xfedfa1e0fd3c0, 0xfee06ae124b72, 0xfee12c0d959b5,
	0xfee1e57900690, 0xfee29734b64d6, 0xfee34150ae46f, 0xfee3e3db89af0,
	0xfee47ee2982a8, 0xfee51271db03c, 0xfee59e9407ef7, 0xfee623528b3e5,
	0xfee6a0b5897a9, 0xfee716c3e0734, 0xfee7858327b3b, 0xfee7ecf7b0674,
	0xfee84d2484a6e, 0xfee8a60b66300, 0xfee8f7accc80f, 0xfee94207e2598,
	0xfee9851a829aa, 0xfee9c0e13481a, 0xfee9f557273b4, 0xfeea22762cc6f,
	0xfeea4836b426d, 0xfeea668fc2d34, 0xfeea7d76ed6bc, 0xfeea8ce04f9ce,
	0xfeea94be83300, 0xfeea9502963d4, 0xfeea8d9c00723, 0xfeea7e789761a,
	0xfeea678481cec, 0xfeea48aa29e4a, 0xfeea21d22e4a2, 0xfee9f2e351fed,
	0xfee9bbc26aef8, 0xfee97c524f2ad, 0xfee93473c0a03, 0xfee8e405574e0,
	0xfee88ae369c44, 0xfee828e7f3dc8, 0xfee7bdea7b854, 0xfee749bff37cb,
	0xfee6cc3a9bd2b, 0xfee64529e004d, 0xfee5b45a32857, 0xfee51994e5784,
	0xfee474a00069d, 0xfee3c53e12c1e, 0xfee30b2e02aa7, 0xfee2462ad81d4,
	0xfee175eb83c2a, 0xfee09a22a1417, 0xfedfb27e3499c, 0xfedebea76213e,
	0xfeddbe422044f, 0xfedcb0ece39a5, 0xfedb964042cc6, 0xfeda6dce9389c,
	0xfed937237e95f, 0xfed7f1c38a80a, 0xfed69d2b9bffe, 0xfed538d06add3,
	0xfed3c41dea3f7, 0xfed23e76a2fac, 0xfed0a732fe617, 0xfecefda07fe08,
	0xfecd4100eb78d, 0xfecb708956e89, 0xfec98b6123096, 0xfec790a0da94e,
	0xfec57f50f31d4, 0xfec356686c938, 0xfec114cb4b30b, 0xfebeb948e6fa6,
	0xfebc429a0b668, 0xfeb9af5ee0cb3, 0xfeb6fe1c98519, 0xfeb42d3ad1f75,
	0xfeb13b00b2d23, 0xfeae2591a02c0, 0xfeaaeae99222d, 0xfea788d8ee2fe,
	0xfea3fcffd73bc, 0xfea044c8dd9ce, 0xfe9c5d62f5612, 0xfe9843ba9477a,
	0xfe93f471d4700, 0xfe8f6bd76c5ad, 0xfe8aa5dc4e8bd, 0xfe859e07ab1c1,
	0xfe804f690a917, 0xfe7ab48823396, 0xfe74c751f6a7c, 0xfe6e8102aa1d9,
	0xfe67da0b6abaf, 0xfe60c9f383055, 0xfe5947338f718, 0xfe51470977256,
	0xfe48bd436f42d, 0xfe3f9bffd1e0d, 0xfe35d35eeb171, 0xfe2b5122fe4d2,
	0xfe2000399552b, 0xfe13c827882e8, 0xfe068c4ee6783, 0xfdf82b02b717d,
	0xfde87c57efe7c, 0xfdd7509c63bce, 0xfdc46e529bee3, 0xfdaf8f82e0252,
	0xfd985e1b2ba43, 0xfd7e6ef48ced0, 0xfd613adbd64d6, 0xfd40149e2efda,
	0xfd1a1a7b4c772, 0xfcee204761f61, 0xfcba8d85e1171, 0xfc7d26ecd2cde,
	0xfc32b2f1e22a1, 0xfbd6581c0b7e7, 0xfb606c40053d6, 0xfac40582a2805,
	0xf9e971e014510, 0xf89fa48a41d49, 0xf66c5f7f02f1a, 0xf1a5a4b331a0a,
}
var wn = [256]float64{
	8.683627060828348e-16, 4.7793301741377593e-17, 6.354352416410258e-17,
	7.454870480493524e-17, 8.329366815173283e-17, 9.068060404526806e-17,
	9.714860076096846e-17, 1.0294750313816509e-16, 1.0823430288059529e-16,
	1.131147019575026e-16, 1.1766359456688471e-16, 1.2193617278400444e-16,
	1.259743991434077e-16, 1.2981099885983e-16, 1.3347203736556521e-16,
	1.3697864842315511e-16, 1.4034823000997335e-16, 1.4359529451821483e-16,
	1.4673208742137644e-16, 1.4976904668172175e-16, 1.5271515003384589e-16,
	1.555781816925582e-16, 1.5836494009092097e-16, 1.6108140175081857e-16,
	1.6373285203782092e-16, 1.663239905823803e-16, 1.6885901708498427e-16,
	1.7134170176385843e-16, 1.737754436569514e-16, 1.7616331922835136e-16,
	1.7850812316814515e-16, 1.808124028564039e-16, 1.830784876467126e-16,
	1.8530851388465636e-16, 1.8750444639224454e-16, 1.8966809700628152e-16,
	1.9180114064694707e-16, 1.9390512930483762e-16, 1.9598150426489938e-16,
	1.9803160682991647e-16, 2.0005668776139063e-16, 2.0205791561939557e-16,
	2.04036384153502e-16, 2.05993118872757e-16, 2.079290829028794e-16,
	2.0984518222246138e-16, 2.1174227035637925e-16, 2.1362115259329185e-16,
	2.154825897846245e-16, 2.1732730177446983e-16, 2.1915597050311456e-16,
	2.2096924282121022e-16, 2.2276773304676727e-16, 2.2455202529302963e-16,
	2.263226755917567e-16, 2.280802138334151e-16, 2.298251455431733e-16,
	2.3155795350934717e-16, 2.3327909927899507e-16, 2.349890245336731e-16,
	2.3668815235689126e-16, 2.3837688840352904e-16, 2.4005562198034833e-16,
	2.417247270457588e-16, 2.4338456313612944e-16, 2.45035476225179e-16,
	2.4667779952231006e-16, 2.483118542151581e-16, 2.4993795016110423e-16,
	2.515563865320341e-16, 2.531674524162133e-16, 2.547714273807808e-16,
	2.5636858199803476e-16, 2.579591783383904e-16, 2.595434704326291e-16,
	2.6112170470582226e-16, 2.626941203851009e-16, 2.6426094988325525e-16,
	2.658224191599747e-16, 2.6737874806238796e-16, 2.689301506464206e-16,
	2.704768354803659e-16, 2.7201900593194673e-16, 2.735568604400485e-16,
	2.7509059277220414e-16, 2.7662039226883326e-16, 2.781464440751553e-16,
	2.796689293616304e-16, 2.811880255337159e-16, 2.8270390643166804e-16,
	2.8421674252106693e-16, 2.8572670107469254e-16, 2.872339463463364e-16,
	2.887386397370925e-16, 2.9024093995463437e-16, 2.917410031659504e-16,
	2.932389831439797e-16, 2.9473503140856054e-16, 2.962292973620791e-16,
	2.977219284201808e-16, 2.9921307013788453e-16, 3.0070286633142155e-16,
	3.021914591960998e-16, 3.036789894204789e-16, 3.051655962971256e-16,
	3.066514178302041e-16, 3.0813659084014326e-16, 3.0962125106561063e-16,
	3.111055332630124e-16, 3.125895713037277e-16, 3.140734982692771e-16,
	3.1555744654461713e-16, 3.1704154790974445e-16, 3.1852593362978663e-16,
	3.200107345437515e-16, 3.214960811520994e-16, 3.2298210370330056e-16,
	3.2446893227953307e-16, 3.259566968816753e-16, 3.2744552751374225e-16,
	3.2893555426691263e-16, 3.3042690740329255e-16, 3.319197174395589e-16,
	3.334141152306249e-16, 3.3491023205346944e-16, 3.36408199691272e-16,
	3.3790815051799436e-16, 3.394102175835521e-16, 3.409145346997195e-16,
	3.4242123652691244e-16, 3.4393045866199745e-16, 3.4544233772727637e-16,
	3.4695701146079997e-16, 3.4847461880816654e-16, 3.4999530001596677e-16,
	3.5151919672703956e-16, 3.530464520777096e-16, 3.545772107971826e-16,
	3.5611161930928127e-16, 3.5764982583671083e-16, 3.591919805080521e-16,
	3.6073823546768757e-16, 3.622887449888749e-16, 3.6384366559019343e-16,
	3.654031561555992e-16, 3.669673780583355e-16, 3.6853649528895996e-16,
	3.7011067458776154e-16, 3.716900855818571e-16, 3.732749009272723e-16,
	3.748652964563299e-16, 3.7646145133068695e-16, 3.7806354820038313e-16,
	3.7967177336928453e-16, 3.8128631696733085e-16, 3.8290737313002033e-16,
	3.845351401855949e-16, 3.861698208504168e-16, 3.878116224330635e-16,
	3.8946075704770037e-16, 3.9111744183733115e-16, 3.9278189920756767e-16,
	3.9445435707160404e-16, 3.961350491071327e-16, 3.978242150259902e-16,
	3.995221008573812e-16, 4.0122895924559043e-16, 4.0294504976316303e-16,
	4.04670639240608e-16, 4.0640600211376074e-16, 4.081514207900323e-16,
	4.0990718603486777e-16, 4.1167359737984636e-16, 4.1345096355397e-16,
	4.1523960293981785e-16, 4.1703984405638327e-16, 4.1885202607056557e-16,
	4.206764993394585e-16, 4.2251362598576456e-16, 4.243637805088701e-16,
	4.2622735043434475e-16, 4.281047370048792e-16, 4.299963559159534e-16,
	4.3190263809983563e-16, 4.338240305618544e-16, 4.3576099727326276e-16,
	4.3771402012543917e-16, 4.396835999506351e-16, 4.4167025761500585e-16,
	4.4367453519024474e-16, 4.456969972107949e-16, 4.477382320243465e-16,
	4.497988532441506e-16, 4.51879501312604e-16, 4.53980845186604e-16,
	4.561035841563454e-16, 4.582484498105623e-16, 4.604162081627235e-16,
	4.626076619543954e-16, 4.64823653153934e-16, 4.670650656708789e-16,
	4.693328283089512e-16, 4.71627917983456e-16, 4.739513632322101e-16,
	4.763042480529397e-16, 4.786877161045007e-16, 4.811029753143727e-16,
	4.83551302940786e-16, 4.860340511447171e-16, 4.885526531349988e-16,
	4.911086299591681e-16, 4.937035980236772e-16, 4.96339277440045e-16,
	4.990175013088311e-16, 5.017402260714605e-16, 5.045095430815269e-16,
	5.07327691573011e-16, 5.101970732338156e-16, 5.131202686303404e-16,
	5.161000557739877e-16, 5.191394311754375e-16, 5.222416337996938e-16,
	5.254101724174328e-16, 5.286488569501704e-16, 5.319618345335188e-16,
	5.353536311813313e-16, 5.388292001330899e-16, 5.423939782198587e-16,
	5.460539519071686e-16, 5.49815735088975e-16, 5.536866612464843e-16,
	5.576748932923575e-16, 5.617895553552448e-16, 5.660408920079487e-16,
	5.704404621288487e-16, 5.750013768917029e-16, 5.797385945721764e-16,
	5.846692893452686e-16, 5.898133176475145e-16, 5.951938149638729e-16,
	6.008379696269235e-16, 6.067780409330819e-16, 6.130527208722697e-16,
	6.19708989457909e-16, 6.268046963298801e-16, 6.34412240712508e-16,
	6.426239659545692e-16, 6.515603317342698e-16, 6.613827885095446e-16,
	6.723150462503459e-16, 6.846803417562237e-16, 6.989718336385731e-16,
	7.159994934828948e-16, 7.372424301797334e-16, 7.658936370804535e-16,
	8.113849337656484e-16,
}
var fn = [256]float64{
	1, 0.9771017012827313, 0.9598790918124159, 0.945198953453078,
	0.9320600759689902, 0.9199915050483602, 0.9087264400605629,
	0.898095921906304, 0.8879846607633999, 0.8783096558161468,
	0.8690086880437932, 0.8600336212030086, 0.8513462584651237,
	0.8429156531184411, 0.8347162929929304, 0.8267268339520942,
	0.8189291916094148, 0.8113078743182199, 0.8038494831763895,
	0.7965423304282546, 0.7893761435711986, 0.7823418326598619,
	0.7754313049861383, 0.7686373158033348, 0.7619533468415464,
	0.7553735065117544, 0.7488924472237266, 0.7425052963446361,
	0.7362075981312666, 0.7299952645658023, 0.7238645334728815,
	0.7178119326349013, 0.7118342488823584, 0.7059285013367973,
	0.7000919181404901, 0.6943219161300326, 0.6886160830085271,
	0.6829721616487914, 0.6773880362225131, 0.6718617199007664,
	0.6663913439123806, 0.6609751477802414, 0.6556114705832247,
	0.6502987431142946, 0.645035480824252, 0.6398202774564391,
	0.6346517992909602, 0.6295287799281284, 0.6244500155502744,
	0.6194143606090393, 0.6144207238920769, 0.6094680649288955,
	0.6045553907005496, 0.5996817526221677, 0.5948462437709913,
	0.590047996335792, 0.5852861792663003, 0.5805599961036835,
	0.5758686829752105, 0.571211506738075, 0.5665877632589518,
	0.5619967758172779, 0.5574378936214863, 0.5529104904285199,
	0.5484139632579211, 0.5439477311926499, 0.5395112342595446,
	0.5351039323830196, 0.5307253044061938, 0.5263748471741866,
	0.5220520746747948, 0.5177565172322006, 0.513487720749743,
	0.5092452459981361, 0.5050286679458288, 0.5008375751284821,
	0.4966715690547963, 0.49253026364614866, 0.48841328470771206,
	0.4843202694289116, 0.4802508659112497, 0.4762047327216837,
	0.47218153846988326, 0.46818096140782217, 0.46420268905027884,
	0.4602464178149235, 0.45631185268077357, 0.4523987068638825,
	0.44850670150921407, 0.44463556539772775, 0.4407850346677699,
	0.4369548525499293, 0.4331447691145741, 0.4293545410313415,
	0.4255839313399006, 0.4218327092313533, 0.4181006498396846,
	0.4143875340427068, 0.41069314827198333, 0.4070172843312482,
	0.4033597392228691, 0.3997203149819319, 0.39609881851754736,
	0.392495061461011, 0.3889088600204649, 0.38534003484173424,
	0.38178841087503157, 0.37825381724723833, 0.3747360871394917,
	0.3712350576698216, 0.3677505697805964, 0.3642824681305497,
	0.36083060099117575, 0.3573948201472905, 0.3539749808015693,
	0.3505709414828812, 0.3471825639582515, 0.34380971314829134,
	0.3404522570459455, 0.33711006663841303, 0.3337830158321087,
	0.3304709813805374, 0.3271738428149589, 0.32389148237773235,
	0.3206237849582305, 0.3173706380312227, 0.3141319315976303,
	0.3109075581275639, 0.30769741250555394, 0.30450139197789644,
	0.3013193961020341, 0.29815132669790134, 0.29499708780116257,
	0.291856585618281, 0.28872972848335393, 0.2856164268166581,
	0.2825165930848494, 0.2794301417627653, 0.27635698929678126,
	0.2732970540696758, 0.27025025636696004, 0.267216518344632,
	0.2641957639983178, 0.261187919133764, 0.2581929113386483,
	0.2552106699556775, 0.25224112605694415, 0.2492842124195171,
	0.2463398635022391, 0.24340801542371232, 0.24048860594144947,
	0.23758157443217398, 0.234686861873253, 0.23180441082524889,
	0.22893416541557776, 0.22607607132326513, 0.22323007576478984,
	0.2203961274810118, 0.2175741767251786, 0.2147641752520087,
	0.21196607630785308, 0.2091798346219358, 0.2064054063986795,
	0.20364274931112164, 0.2008918224954315, 0.19815258654653828,
	0.1954250035148857, 0.192709036904329, 0.19000465167119332,
	0.18731181422451715, 0.18463049242750473, 0.18196065560021674,
	0.17930227452353056, 0.17665532144440677, 0.17401977008249953,
	0.1713955956381557, 0.16878277480185033, 0.16618128576511007,
	0.16359110823298295, 0.16101222343811766, 0.15844461415652022,
	0.15588826472506456, 0.15334316106083767, 0.15080929068241017,
	0.1482866427331287, 0.14577520800653793, 0.14327497897404712,
	0.1407859498149683, 0.13830811644906432, 0.13584147657175735,
	0.13338602969216284, 0.13094177717412817, 0.12850872228047364,
	0.12608687022065035, 0.1236762282020514, 0.12127680548523544,
	0.1188886134433458, 0.11651166562603717, 0.11414597782825531,
	0.11179156816424568, 0.10944845714721012, 0.10711666777507302,
	0.10479622562286714, 0.10248715894230628, 0.10018949876917202,
	0.09790327903921563, 0.09562853671335333, 0.09336531191302662,
	0.09111364806670073, 0.08887359206859424, 0.08664519445086778,
	0.08442850957065465, 0.08222359581349568, 0.08003051581494751,
	0.07784933670237221, 0.07568013035919496, 0.07352297371424099,
	0.07137794905914197, 0.06924514439725027, 0.06712465382802399,
	0.06501657797147044, 0.06292102443797785, 0.060838108349751806,
	0.058767952921137984, 0.05671069010639947, 0.054666461325077916,
	0.05263541827697365, 0.05061772386112179, 0.048613553216035145,
	0.046623094902089664, 0.044646552251446536, 0.04268414491661938,
	0.04073611065607875, 0.038802707404656925, 0.03688421568869116,
	0.03498094146183307, 0.0330932194586887, 0.03122141719202369,
	0.02936593975823011, 0.02752723566969332, 0.025705804008632656,
	0.023902203305873237, 0.022117062707379922, 0.020351096230109354,
	0.01860512127578335, 0.01688008315259584, 0.015177088307982072,
	0.013497450601780807, 0.011842757857943104, 0.0102149714397311,
	0.008616582769422919, 0.00705087547139211, 0.005522403299264754,
	0.0040379725933718715, 0.002609072746106363, 0.0012602859304985978,
}