You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2021/08/12 16:33:11 UTC
[commons-rng] 01/03: Add ziggurat samplers with a table size of 512
to the performance test
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git
commit 387a2e31a53e33eea5c15b6469ba9b967e418b45
Author: aherbert <ah...@apache.org>
AuthorDate: Thu Aug 12 16:02:28 2021 +0100
Add ziggurat samplers with a table size of 512 to the performance test
---
.../distribution/ZigguratSamplerPerformance.java | 1184 +++++++++++++++++++-
1 file changed, 1180 insertions(+), 4 deletions(-)
diff --git a/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/distribution/ZigguratSamplerPerformance.java b/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/distribution/ZigguratSamplerPerformance.java
index 1b9456a..c5a50be 100644
--- a/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/distribution/ZigguratSamplerPerformance.java
+++ b/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/distribution/ZigguratSamplerPerformance.java
@@ -82,6 +82,8 @@ public class ZigguratSamplerPerformance {
private static final String MOD_GAUSSIAN_INLINING_SIMPLE_OVERHANGS = "ModGaussianInliningSimpleOverhangs";
/** The name for the {@link ModifiedZigguratNormalizedGaussianSamplerIntMap}. */
private static final String MOD_GAUSSIAN_INT_MAP = "ModGaussianIntMap";
+ /** The name for the {@link ModifiedZigguratNormalizedGaussianSampler512} using a table size of 512. */
+ private static final String MOD_GAUSSIAN_512 = "ModGaussian512";
/** The name for the {@link ModifiedZigguratExponetialSampler}.
* This is a base implementation of McFarland's ziggurat method. */
@@ -96,6 +98,8 @@ public class ZigguratSamplerPerformance {
private static final String MOD_EXPONENTIAL_RECURSION = "ModExponentialRecursion";
/** The name for the {@link ModifiedZigguratExponentialSamplerIntMap}. */
private static final String MOD_EXPONENTIAL_INT_MAP = "ModExponentialIntMap";
+ /** The name for the {@link ModifiedZigguratExponentialSampler512} using a table size of 512. */
+ private static final String MOD_EXPONENTIAL_512 = "ModExponential512";
/**
* The value.
@@ -232,10 +236,10 @@ public class ZigguratSamplerPerformance {
EXPONENTIAL,
// Experimental McFarland Gaussian ziggurat samplers
MOD_GAUSSIAN2, MOD_GAUSSIAN_SIMPLE_OVERHANGS, MOD_GAUSSIAN_INLINING,
- MOD_GAUSSIAN_INLINING_SIMPLE_OVERHANGS, MOD_GAUSSIAN_INT_MAP,
+ MOD_GAUSSIAN_INLINING_SIMPLE_OVERHANGS, MOD_GAUSSIAN_INT_MAP, MOD_GAUSSIAN_512,
// Experimental McFarland Gaussian ziggurat samplers
MOD_EXPONENTIAL2, MOD_EXPONENTIAL_SIMPLE_OVERHANGS, MOD_EXPONENTIAL_INLINING,
- MOD_EXPONENTIAL_LOOP, MOD_EXPONENTIAL_RECURSION, MOD_EXPONENTIAL_INT_MAP})
+ MOD_EXPONENTIAL_LOOP, MOD_EXPONENTIAL_RECURSION, MOD_EXPONENTIAL_INT_MAP, MOD_EXPONENTIAL_512})
private String type;
/** The sampler. */
@@ -284,6 +288,8 @@ public class ZigguratSamplerPerformance {
return new ModifiedZigguratNormalizedGaussianSamplerInliningSimpleOverhangs(rng);
} else if (MOD_GAUSSIAN_INT_MAP.equals(type)) {
return new ModifiedZigguratNormalizedGaussianSamplerIntMap(rng);
+ } else if (MOD_GAUSSIAN_512.equals(type)) {
+ return new ModifiedZigguratNormalizedGaussianSampler512(rng);
} else if (MOD_EXPONENTIAL2.equals(type)) {
return new ModifiedZigguratExponentialSampler(rng);
} else if (MOD_EXPONENTIAL_SIMPLE_OVERHANGS.equals(type)) {
@@ -296,6 +302,8 @@ public class ZigguratSamplerPerformance {
return new ModifiedZigguratExponentialSamplerRecursion(rng);
} else if (MOD_EXPONENTIAL_INT_MAP.equals(type)) {
return new ModifiedZigguratExponentialSamplerIntMap(rng);
+ } else if (MOD_EXPONENTIAL_512.equals(type)) {
+ return new ModifiedZigguratExponentialSampler512(rng);
} else {
throw new IllegalStateException("Unknown type: " + type);
}
@@ -339,10 +347,10 @@ public class ZigguratSamplerPerformance {
EXPONENTIAL,
// Experimental McFarland Gaussian ziggurat samplers
MOD_GAUSSIAN2, MOD_GAUSSIAN_SIMPLE_OVERHANGS, MOD_GAUSSIAN_INLINING,
- MOD_GAUSSIAN_INLINING_SIMPLE_OVERHANGS, MOD_GAUSSIAN_INT_MAP,
+ MOD_GAUSSIAN_INLINING_SIMPLE_OVERHANGS, MOD_GAUSSIAN_INT_MAP, MOD_GAUSSIAN_512,
// Experimental McFarland Gaussian ziggurat samplers
MOD_EXPONENTIAL2, MOD_EXPONENTIAL_SIMPLE_OVERHANGS, MOD_EXPONENTIAL_INLINING,
- MOD_EXPONENTIAL_LOOP, MOD_EXPONENTIAL_RECURSION, MOD_EXPONENTIAL_INT_MAP})
+ MOD_EXPONENTIAL_LOOP, MOD_EXPONENTIAL_RECURSION, MOD_EXPONENTIAL_INT_MAP, MOD_EXPONENTIAL_512})
private String type;
/** The size. */
@@ -1565,6 +1573,606 @@ public class ZigguratSamplerPerformance {
}
/**
+ * Modified Ziggurat method for sampling from a Gaussian distribution with mean 0 and standard deviation 1.
+ *
+ * <p>Uses the algorithm from McFarland, C.D. (2016).
+ *
+ * <p>This is a copy of {@link ModifiedZigguratNormalizedGaussianSampler} using
+ * a table size of 512.
+ */
+ static class ModifiedZigguratNormalizedGaussianSampler512 implements ContinuousSampler {
+ /** Maximum i value for early exit. */
+ protected static final int I_MAX = 509;
+ /** The point where the Gaussian switches from convex to concave. */
+ protected static final int J_INFLECTION = 410;
+ /** Used for largest deviations of f(x) from y_i. This is negated on purpose. */
+ protected static final long MAX_IE = -2284356979160975476L;
+ /** Used for largest deviations of f(x) from y_i. */
+ protected static final long MIN_IE = 764138791244619676L;
+ /** Beginning of tail. */
+ protected static final double X_0 = 3.8358644648571882;
+ /** 1/X_0. */
+ protected static final double ONE_OVER_X_0 = 1d / X_0;
+
+ /** The alias map. */
+ private static final int[] MAP = {0, 0, 480, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 1, 1, 1, 1, 1, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509,
+ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508,
+ 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 507, 507, 507, 507, 507, 507, 507, 507,
+ 507, 507, 507, 507, 507, 507, 506, 506, 506, 506, 506, 506, 506, 506, 506, 506, 505, 505, 505, 505, 505,
+ 505, 505, 505, 504, 504, 504, 504, 504, 504, 503, 503, 503, 503, 503, 502, 502, 502, 502, 501, 501, 501,
+ 501, 500, 500, 500, 500, 499, 499, 499, 498, 498, 498, 497, 497, 496, 496, 495, 495, 494, 494, 493, 493,
+ 492, 491, 490, 489, 488, 487, 486, 484, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 7, 8, 0, 0, 0, 0, 0, 0, 0,
+ 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 496, 497, 498, 499, 500, 501,
+ 502, 503, 504, 505, 506, 507, 508, 509, 1, 0, 0};
+ /** The alias inverse PMF. */
+ private static final long[] IPMF = {9223372036854775296L, 3232176979959565312L, 2248424156373566976L,
+ 5572490326155894272L, 3878549168685540352L, 6596558088755235840L, 7126388452799016960L,
+ 5909258326277172224L, 6789036995587703808L, 8550801776550481920L, 7272880214327450112L,
+ 6197723851568405504L, 5279475843641833984L, 4485290838628302848L, 3790998004182467072L,
+ 3178396845257682944L, 2633509168847815680L, 2145413694861947904L, 1705448049989382144L,
+ 1306649397437548544L, 943354160611131392L, 610906287013685760L, 305441095029422592L, 23722736478678016L,
+ -236979677660888064L, -478987634076675072L, -704287768537463808L, -914590611781799424L,
+ -1111377331889550848L, -1295937239757415424L, -1469398133880157184L, -1632751030331424768L,
+ -1786870462753421312L, -1932531249141885952L, -2070422432472262144L, -2201158928905888256L,
+ -2325291321647773696L, -2443314131355272192L, -2555672836734271488L, -2662769858897092096L,
+ -2764969686945558528L, -2862603283332330496L, -2955971885350600192L, -3045350299719277056L,
+ -3130989762881722368L, -3213120439420999168L, -3291953604062304256L, -3367683558060156416L,
+ -3440489316130714624L, -3510536092827323904L, -3577976620246562816L, -3642952314681374720L,
+ -3705594315191049216L, -3766024408614111744L, -3824355856527138304L, -3880694134271785472L,
+ -3935137594960746496L, -3987778065544580608L, -4038701385199136256L, -4087987887601244160L,
+ -4135712841168144384L, -4181946844655158784L, -4226756186527602176L, -4270203172038951424L,
+ -4312346420932761088L, -4353241136943226880L, -4392939356053354496L, -4431490172784719360L,
+ -4468939945001798656L, -4505332485123679232L, -4540709232733563392L, -4575109415088551424L,
+ -4608570193416988672L, -4641126797904314880L, -4672812652574308352L, -4703659490673809920L,
+ -4733697460624237568L, -4762955224068688384L, -4791460047779233792L, -4819237887169053184L,
+ -4846313464821579264L, -4872710343112062464L, -4898450992673160192L, -4923556853979476992L,
+ -4948048396148470272L, -4971945172796024320L, -4995265870892981248L, -5018028360085760000L,
+ -5040249735872740864L, -5061946361747427840L, -5083133907806415360L, -5103827387715595776L,
+ -5124041191022579712L, -5143789117574014464L, -5163084406061926400L, -5181939762086439936L,
+ -5200367384806330368L, -5218378992989818368L, -5235985846759801344L, -5253198770233210880L,
+ -5270028172706144256L, -5286484068673344512L, -5302576093914087424L, -5318313526819882496L,
+ -5333705300501412864L, -5348760022140801536L, -5363485985612222976L, -5377891185738658816L,
+ -5391983331261941760L, -5405769858949649408L, -5419257942659722240L, -5432454506730834944L,
+ -5445366236058309120L, -5457999585571643392L, -5470360790218524160L, -5482455874386169344L,
+ -5494290660050575872L, -5505870774716076032L, -5517201660378635264L, -5528288579187974144L,
+ -5539136622578390528L, -5549750716118886400L, -5560135626660535808L, -5570295969034180608L,
+ -5580236210799400960L, -5589960678379259904L, -5599473562706778112L, -5608778923054202880L,
+ -5617880692891545088L, -5626782684460370944L, -5635488592684399104L, -5644001999389030912L,
+ -5652326378260390400L, -5660465096501542912L, -5668421421481986048L, -5676198522069054464L,
+ -5683799472034193408L, -5691227254524439552L, -5698484764964738048L, -5705574811911234048L,
+ -5712500123062644224L, -5719263345561367040L, -5725867049400364032L, -5732313730758826496L,
+ -5738605812086640640L, -5744745647569117184L, -5750735522378352640L, -5756577656307920896L,
+ -5762274206097785856L, -5767827266307192832L, -5773238871631092224L, -5778510999439789056L,
+ -5783645569528274432L, -5788644448981466624L, -5793509449834629120L, -5798242334409694208L,
+ -5802844813858308096L, -5807318551213207040L, -5811665162349513216L, -5815886217028536832L,
+ -5819983240762728448L, -5823957715198579712L, -5827811080259974144L, -5831544734136989696L,
+ -5835160035614893056L, -5838658304467378688L, -5842040821904171520L, -5845308832880873984L,
+ -5848463546172629504L, -5851506134738812416L, -5854437738541255168L, -5857259462674584064L,
+ -5859972381032173568L, -5862577534420617216L, -5865075933349880320L, -5867468558168720896L,
+ -5869756358001916928L, -5871940255655389696L, -5874021142765756416L, -5875999885243720704L,
+ -5877877321138562048L, -5879654262030006784L, -5881331493491406336L, -5882909775710032384L,
+ -5884389844282934784L, -5885772409590032896L, -5887058159412298240L, -5888247756760180736L,
+ -5889341841868359680L, -5890341033726286848L, -5891245927036046336L, -5892057096967517184L,
+ -5892775095254208000L, -5893400454293159424L, -5893933684945675776L, -5894375277894875136L,
+ -5894725704281316864L, -5894985415097101824L, -5895154842211865088L, -5895234398367037440L,
+ -5895224478119281152L, -5895125456527683584L, -5894937691150572032L, -5894661521100592128L,
+ -5894297268546692608L, -5893845237129657344L, -5893305713928932352L, -5892678968199164928L,
+ -5891965253512273920L, -5891164805272775680L, -5890277843462263808L, -5889304570970719232L,
+ -5888245175227536896L, -5887099827242714112L, -5885868681480997376L, -5884551878016265728L,
+ -5883149540187518976L, -5881661776186659840L, -5880088679051159040L, -5878430325617481216L,
+ -5876686779113256448L, -5874858086097725440L, -5872944278695313920L, -5870945374625903616L,
+ -5868861375946597376L, -5866692270114584576L, -5864438029808936448L, -5862098613329829376L,
+ -5859673963988850688L, -5857164010304659456L, -5854568667030923264L, -5851887832571710976L,
+ -5849121393007995904L, -5846269217914838016L, -5843331163565322752L, -5840307071023708160L,
+ -5837196767034538496L, -5834000063619345920L, -5830716757850101760L, -5827346633080182272L,
+ -5823889457015247872L, -5820344982925702656L, -5816712949734398464L, -5812993080309509120L,
+ -5809185084612210688L, -5805288655397134848L, -5801303472071718912L, -5797229197542626816L,
+ -5793065480979245568L, -5788811954902762496L, -5784468237204753408L, -5780033929729368064L,
+ -5775508619016246784L, -5770891876025206272L, -5766183254901072896L, -5761382294937170432L,
+ -5756488518102026240L, -5751501431126126080L, -5746420523619011584L, -5741245267817476608L,
+ -5735975121281433088L, -5730609522034737152L, -5725147892326605312L, -5719589637112302080L,
+ -5713934142693986816L, -5708180778990178816L, -5702328896016054784L, -5696377827537145856L,
+ -5690326887295941632L, -5684175370772383744L, -5677922555045085184L, -5671567696296352256L,
+ -5665110033102450176L, -5658548782530205696L, -5651883142913629696L, -5645112290875286016L,
+ -5638235383069228544L, -5631251554336663040L, -5624159919711433728L, -5616959570005672448L,
+ -5609649575759112704L, -5602228984633701376L, -5594696820961281536L, -5587052085776743936L,
+ -5579293757104064512L, -5571420787942931456L, -5563432107812764160L, -5555326619765914112L,
+ -5547103202855799296L, -5538760709287606272L, -5530297965182673920L, -5521713769559916032L,
+ -5513006894391551488L, -5504176082674265088L, -5495220049712259584L, -5486137481881783808L,
+ -5476927034862822400L, -5467587334392330752L, -5458116976167262720L, -5448514522422561280L,
+ -5438778504885873664L, -5428907421454137344L, -5418899736307948032L, -5408753879414383104L,
+ -5398468245670757888L, -5388041193950201856L, -5377471046142717440L, -5366756087011503104L,
+ -5355894562291467776L, -5344884679094671360L, -5333724604104164352L, -5322412462390110720L,
+ -5310946337190221824L, -5299324269391752192L, -5287544254227943936L, -5275604243076108288L,
+ -5263502140384954880L, -5251235803114780672L, -5238803040260463616L, -5226201609860500992L,
+ -5213429220396639232L, -5200483526689941504L, -5187362130814278656L, -5174062579249043456L,
+ -5160582362536272384L, -5146918913003260928L, -5133069603645442048L, -5119031746455840768L,
+ -5104802590846193664L, -5090379322288435200L, -5075759059905230848L, -5060938855168388608L,
+ -5045915690136155648L, -5030686475123909120L, -5015248047351192576L, -4999597168201581568L,
+ -4983730521429875200L, -4967644711103290880L, -4951336259902648320L, -4934801604331100672L,
+ -4918037096313518080L, -4901038996556133376L, -4883803475152384512L, -4866326606521733120L,
+ -4848604368549652480L, -4830632638500906496L, -4812407189788950016L, -4793923690356844544L,
+ -4775177697581510656L, -4756164656502554112L, -4736879895545858048L, -4717318622225770496L,
+ -4697475921931613696L, -4677346750468523008L, -4656925933129603072L, -4636208158837948416L,
+ -4615187976257695744L, -4593859789223797248L, -4572217851458716672L, -4550256263721420288L,
+ -4527968965738787328L, -4505349732602470400L, -4482392170596992000L, -4459089707595035648L,
+ -4435435591206243840L, -4411422880135513088L, -4387044438367173632L, -4362292928394443264L,
+ -4337160804216032256L, -4311640303794398208L, -4285723442340192768L, -4259402002490114048L,
+ -4232667527557880832L, -4205511312870738944L, -4177924395156510720L, -4149897544928282624L,
+ -4121421255517056000L, -4092485732978126848L, -4063080884857030656L, -4033196309983527424L,
+ -4002821285452889600L, -3971944754955299840L, -3940555315053852672L, -3908641203541062144L,
+ -3876190282046383616L, -3843190024121122816L, -3809627498134461952L, -3775489350771450880L,
+ -3740761791237469184L, -3705430570995169280L, -3669480966726291456L, -3632897760460073472L,
+ -3595665216111472128L, -3557767061510936064L, -3519186461826909184L, -3479905997291117056L,
+ -3439907636209809920L, -3399172709277578752L, -3357681881315035136L, -3315415118925273600L,
+ -3272351662607639040L, -3228469989824430592L, -3183747783206633472L, -3138161891189001728L,
+ -3091688288710896128L, -3044302038074020352L, -2995977242912180224L, -2946687001898157056L,
+ -2896403361643595776L, -2845097261899269632L, -2792738483041489920L, -2739295585832944128L,
+ -2684735849802800128L, -2629025208318833152L, -2572128177407577088L, -2514007780971290112L,
+ -2454625474210264064L, -2393941056301004288L, -2331912582463081472L, -2268496267820575232L,
+ -2203646385063500288L, -2137315156805725696L, -2069452637212809728L, -2000006589650226176L,
+ -1928922352643083264L, -1856142697389204480L, -1781607676495585792L, -1705254458055283200L,
+ -1627017152968592896L, -1546826624346926592L, -1464610284716681216L, -1380291880647352832L,
+ -1293791253775522304L, -1205024091744495104L, -1113901652592291328L, -1020330470192921600L,
+ -924212036524504576L, -825442455107712512L, -723912067910252544L, -619505050467681792L,
+ -512098970851033088L, -401564310549775872L, -287763946399309312L, -170552579279989760L, -49776119384483328L,
+ 74728993660240384L, 203136528144344576L, 335631271254235136L, 472409917558910464L, 613682045009508352L,
+ 759671188745830912L, 910616024566752768L, 1066771674457471488L, 1228411150191648768L, 1395826950915523584L,
+ 1569332837797146112L, 1749265802232386560L, 1935988261896280064L, 2129890506883624960L,
+ 2331393435927328256L, 2540951622664266752L, 2759056758111070720L, 2986241520688130560L,
+ 3223083948864353280L, 3470212380253329408L, 3728311054271952896L, 3998126479196178432L,
+ 4280474694750398976L, 4576249573583467520L, 4886432342140325376L, 5212102538692988928L,
+ 5554450665570580992L, 5914792845058133504L, 6294587870200374272L, 6695457110790894080L,
+ 7119207852916254720L, 7567860785399318528L, 8043682516018548736L, 8549224231795344384L,
+ 9087367898325182976L, 2686433895585048064L, 3738049383351049728L, 5447119168340997632L,
+ 7862383433967084544L, 3564125970404768256L, 7561510489765503488L, 4795007330430237184L,
+ 2822776087249664512L, 1739199416312530432L, 1651067950292976640L, 2680178586723521024L,
+ 4966620264299254784L, 8672981687287425024L, 5102073364374541824L, 2973953244697943040L,
+ 2586847729538911744L, 4294392489026305536L, 8524338069805147648L, 5657549542711693824L,
+ 6039225349920109568L, -188437589949716992L, -1600155058499635712L, 3512467924097231872L,
+ 5888549710424099840L, 8328892371572499456L, 3607211374099356160L, 952847323024169472L,
+ -3124063727137777664L, -844200026382571008L, 1173948101715934208L, -9223372036854775808L,
+ -9223372036854775808L};
+ /**
+ * The precomputed ziggurat lengths, denoted X_i in the main text. X_i = length of
+ * ziggurat layer i.
+ */
+ private static final double[] X = {4.1588525861581104e-19, 3.9503459916661627e-19, 3.821680975424891e-19,
+ 3.727004572118549e-19, 3.6514605982514084e-19, 3.5882746800626676e-19, 3.533765597048754e-19,
+ 3.485701802710972e-19, 3.4426246437790343e-19, 3.403526438955331e-19, 3.367680884141069e-19,
+ 3.334546590044289e-19, 3.303708833135166e-19, 3.274842648111545e-19, 3.2476884984205335e-19,
+ 3.2220356973333147e-19, 3.1977107871867837e-19, 3.174569193558674e-19, 3.152489103227302e-19,
+ 3.1313668890638164e-19, 3.111113634164771e-19, 3.091652452001866e-19, 3.0729163928347323e-19,
+ 3.0548467885197293e-19, 3.0373919296832198e-19, 3.0205059980435e-19, 3.0041481968537306e-19,
+ 2.9882820368030914e-19, 2.9728747450808126e-19, 2.957896772888449e-19, 2.943321382295927e-19,
+ 2.929124297535286e-19, 2.915283409000532e-19, 2.901778520645554e-19, 2.8885911333390034e-19,
+ 2.875704258185245e-19, 2.8631022549560207e-19, 2.8507706916730813e-19, 2.8386962220934334e-19,
+ 2.8268664784176013e-19, 2.815269976998848e-19, 2.803896035201538e-19, 2.7927346978581e-19,
+ 2.7817766720204774e-19, 2.7710132689045585e-19, 2.7604363520934134e-19, 2.750038291204046e-19,
+ 2.739811920338075e-19, 2.7297505007336127e-19, 2.7198476871169526e-19, 2.710097497321303e-19,
+ 2.700494284797851e-19, 2.691032713693778e-19, 2.681707736213845e-19, 2.6725145720181144e-19,
+ 2.6634486894391515e-19, 2.6545057883285584e-19, 2.6456817843655206e-19, 2.636972794679811e-19,
+ 2.6283751246588273e-19, 2.6198852558231173e-19, 2.6114998346678357e-19, 2.6032156623788965e-19,
+ 2.5950296853425164e-19, 2.586938986375541e-19, 2.5789407766116098e-19, 2.5710323879849453e-19,
+ 2.5632112662595285e-19, 2.555474964556656e-19, 2.547821137338583e-19, 2.5402475348100586e-19,
+ 2.532751997703282e-19, 2.5253324524150594e-19, 2.517986906467905e-19, 2.5107134442694197e-19,
+ 2.503510223146645e-19, 2.4963754696341833e-19, 2.4893074759967754e-19, 2.4823045969687053e-19,
+ 2.475365246693953e-19, 2.4684878958523816e-19, 2.4616710689584975e-19, 2.4549133418204393e-19,
+ 2.448213339147886e-19, 2.4415697322984843e-19, 2.4349812371532436e-19, 2.4284466121121044e-19,
+ 2.42196465620158e-19, 2.4155342072870043e-19, 2.409154140382495e-19, 2.402823366052261e-19,
+ 2.3965408288973736e-19, 2.390305506122548e-19, 2.384116406177891e-19, 2.377972567470941e-19,
+ 2.3718730571446517e-19, 2.3658169699173055e-19, 2.3598034269805933e-19, 2.353831574952395e-19,
+ 2.3479005848810095e-19, 2.342009651297822e-19, 2.336157991315592e-19, 2.33034484376974e-19,
+ 2.3245694684001817e-19, 2.3188311450714236e-19, 2.313129173028786e-19, 2.307462870188744e-19,
+ 2.3018315724615257e-19, 2.2962346331042115e-19, 2.290671422102686e-19, 2.285141325580919e-19,
+ 2.279643745236112e-19, 2.2741780977983687e-19, 2.2687438145136136e-19, 2.263340340648552e-19,
+ 2.2579671350165625e-19, 2.2526236695234495e-19, 2.247309428732065e-19, 2.2420239094448635e-19,
+ 2.236766620303496e-19, 2.231537081404625e-19, 2.2263348239311565e-19, 2.2211593897981584e-19,
+ 2.216010331312762e-19, 2.2108872108473813e-19, 2.205789600525628e-19, 2.200717081920328e-19,
+ 2.1956692457630854e-19, 2.1906456916648504e-19, 2.185646027847011e-19, 2.1806698708825153e-19,
+ 2.1757168454465786e-19, 2.170786584076557e-19, 2.1658787269405759e-19, 2.1609929216145222e-19,
+ 2.156128822867056e-19, 2.1512860924522763e-19, 2.1464643989097195e-19, 2.1416634173713822e-19,
+ 2.1368828293754638e-19, 2.1321223226865536e-19, 2.1273815911219872e-19, 2.122660334384123e-19,
+ 2.1179582578982903e-19, 2.1132750726561794e-19, 2.1086104950644545e-19, 2.103964246798376e-19,
+ 2.099336054660232e-19, 2.09472565044239e-19, 2.090132770794785e-19, 2.0855571570966692e-19,
+ 2.0809985553324565e-19, 2.0764567159715066e-19, 2.0719313938516928e-19, 2.0674223480666103e-19,
+ 2.0629293418562883e-19, 2.0584521425012706e-19, 2.05399052121994e-19, 2.049544253068964e-19,
+ 2.0451131168467476e-19, 2.0406968949997815e-19, 2.0362953735317784e-19, 2.0319083419154967e-19,
+ 2.027535593007156e-19, 2.0231769229633464e-19, 2.0188321311603464e-19, 2.014501020115762e-19,
+ 2.0101833954124038e-19, 2.0058790656243254e-19, 2.0015878422449446e-19, 1.9973095396171768e-19,
+ 1.9930439748655098e-19, 1.988790967829954e-19, 1.984550341001801e-19, 1.9803219194611336e-19,
+ 1.9761055308160207e-19, 1.9719010051433485e-19, 1.967708174931225e-19, 1.9635268750229097e-19,
+ 1.9593569425622174e-19, 1.955198216940345e-19, 1.9510505397440756e-19, 1.9469137547053159e-19,
+ 1.9427877076519196e-19, 1.9386722464597592e-19, 1.9345672210060023e-19, 1.9304724831235547e-19,
+ 1.9263878865566334e-19, 1.9223132869174325e-19, 1.918248541643845e-19, 1.9141935099582133e-19,
+ 1.9101480528270662e-19, 1.9061120329218205e-19, 1.9020853145804105e-19, 1.8980677637698202e-19,
+ 1.8940592480494855e-19, 1.8900596365355448e-19, 1.8860687998659074e-19, 1.8820866101661152e-19,
+ 1.8781129410159744e-19, 1.874147667416932e-19, 1.8701906657601756e-19, 1.8662418137954315e-19,
+ 1.862300990600444e-19, 1.85836807655111e-19, 1.8544429532922543e-19, 1.8505255037090195e-19,
+ 1.8466156118988594e-19, 1.8427131631441095e-19, 1.8388180438851245e-19, 1.8349301416939593e-19,
+ 1.8310493452485817e-19, 1.8271755443075968e-19, 1.823308629685471e-19, 1.8194484932282376e-19,
+ 1.8155950277896707e-19, 1.8117481272079125e-19, 1.8079076862825417e-19, 1.804073600752067e-19,
+ 1.8002457672718337e-19, 1.7964240833923322e-19, 1.7926084475378945e-19, 1.7887987589857656e-19,
+ 1.7849949178455405e-19, 1.7811968250389552e-19, 1.7774043822800183e-19, 1.773617492055474e-19,
+ 1.7698360576055882e-19, 1.7660599829052424e-19, 1.7622891726453298e-19, 1.7585235322144435e-19,
+ 1.754762967680843e-19, 1.751007385774697e-19, 1.7472566938705867e-19, 1.743510799970264e-19,
+ 1.7397696126856576e-19, 1.7360330412221144e-19, 1.7323009953618705e-19, 1.7285733854477456e-19,
+ 1.7248501223670475e-19, 1.7211311175356858e-19, 1.7174162828824813e-19, 1.7137055308336676e-19,
+ 1.709998774297575e-19, 1.7062959266494937e-19, 1.7025969017167022e-19, 1.6989016137636627e-19,
+ 1.6952099774773704e-19, 1.6915219079528517e-19, 1.6878373206788065e-19, 1.6841561315233867e-19,
+ 1.6804782567201046e-19, 1.6768036128538652e-19, 1.6731321168471171e-19, 1.6694636859461146e-19,
+ 1.6657982377072854e-19, 1.662135689983699e-19, 1.6584759609116298e-19, 1.6548189688972057e-19,
+ 1.6511646326031438e-19, 1.6475128709355596e-19, 1.6438636030308492e-19, 1.640216748242637e-19,
+ 1.6365722261287829e-19, 1.632929956438448e-19, 1.6292898590992037e-19, 1.625651854204191e-19,
+ 1.6220158619993133e-19, 1.618381802870466e-19, 1.6147495973307924e-19, 1.6111191660079618e-19,
+ 1.6074904296314645e-19, 1.6038633090199211e-19, 1.600237725068394e-19, 1.5966135987357025e-19,
+ 1.5929908510317342e-19, 1.5893694030047434e-19, 1.5857491757286376e-19, 1.5821300902902412e-19,
+ 1.5785120677765333e-19, 1.5748950292618545e-19, 1.5712788957950753e-19, 1.5676635883867226e-19,
+ 1.5640490279960565e-19, 1.560435135518094e-19, 1.5568218317705714e-19, 1.553209037480841e-19,
+ 1.5495966732726971e-19, 1.545984659653122e-19, 1.54237291699895e-19, 1.5387613655434405e-19,
+ 1.5351499253627542e-19, 1.531538516362328e-19, 1.527927058263138e-19, 1.5243154705878517e-19,
+ 1.5207036726468514e-19, 1.517091583524134e-19, 1.5134791220630703e-19, 1.509866206852025e-19,
+ 1.506252756209824e-19, 1.5026386881710618e-19, 1.499023920471249e-19, 1.4954083705317816e-19,
+ 1.4917919554447328e-19, 1.488174591957453e-19, 1.4845561964569755e-19, 1.480936684954214e-19,
+ 1.4773159730679478e-19, 1.4736939760085815e-19, 1.470070608561676e-19, 1.4664457850712328e-19,
+ 1.462819419422733e-19, 1.4591914250259098e-19, 1.4555617147972526e-19, 1.4519302011422298e-19,
+ 1.4482967959372176e-19, 1.4446614105111258e-19, 1.4410239556267103e-19, 1.437384341461557e-19,
+ 1.433742477588729e-19, 1.4300982729570602e-19, 1.4264516358710902e-19, 1.4228024739706157e-19,
+ 1.4191506942098562e-19, 1.4154962028362133e-19, 1.4118389053686103e-19, 1.4081787065753974e-19,
+ 1.4045155104518092e-19, 1.4008492201969533e-19, 1.3971797381903188e-19, 1.3935069659677833e-19,
+ 1.3898308041971047e-19, 1.3861511526528749e-19, 1.3824679101909196e-19, 1.3787809747221246e-19,
+ 1.3750902431856644e-19, 1.3713956115216185e-19, 1.3676969746429448e-19, 1.3639942264067964e-19,
+ 1.3602872595851507e-19, 1.3565759658347313e-19, 1.3528602356661948e-19, 1.3491399584125558e-19,
+ 1.345415022196824e-19, 1.3416853138988266e-19, 1.3379507191211783e-19, 1.3342111221543818e-19,
+ 1.3304664059410112e-19, 1.3267164520389587e-19, 1.3229611405837e-19, 1.3192003502495473e-19,
+ 1.315433958209853e-19, 1.311661840096121e-19, 1.3078838699559864e-19, 1.3040999202100255e-19,
+ 1.3003098616073445e-19, 1.2965135631799062e-19, 1.2927108921955436e-19, 1.2889017141096131e-19,
+ 1.285085892515231e-19, 1.281263289092043e-19, 1.2774337635534646e-19, 1.2735971735923388e-19,
+ 1.269753374824942e-19, 1.2659022207332785e-19, 1.262043562605593e-19, 1.2581772494750294e-19,
+ 1.2543031280563616e-19, 1.250421042680721e-19, 1.2465308352282341e-19, 1.2426323450584884e-19,
+ 1.238725408938736e-19, 1.2348098609697396e-19, 1.230885532509165e-19, 1.2269522520924136e-19,
+ 1.22300984535079e-19, 1.2190581349268875e-19, 1.2150969403870742e-19, 1.2111260781309555e-19,
+ 1.2071453612976755e-19, 1.203154599668928e-19, 1.199153599568521e-19, 1.1951421637583513e-19,
+ 1.191120091330619e-19, 1.187087177596121e-19, 1.1830432139684355e-19, 1.1789879878438187e-19,
+ 1.1749212824766058e-19, 1.1708428768499157e-19, 1.1667525455414306e-19, 1.1626500585840243e-19,
+ 1.1585351813209874e-19, 1.1544076742555945e-19, 1.150267292894733e-19, 1.1461137875863088e-19,
+ 1.1419469033501178e-19, 1.1377663797018575e-19, 1.1335719504699387e-19, 1.129363343604726e-19,
+ 1.1251402809798253e-19, 1.1209024781850075e-19, 1.1166496443103302e-19, 1.112381481720998e-19,
+ 1.1080976858224708e-19, 1.1037979448152952e-19, 1.0994819394391104e-19, 1.0951493427052315e-19,
+ 1.0907998196171864e-19, 1.0864330268785362e-19, 1.0820486125872634e-19, 1.0776462159159718e-19,
+ 1.0732254667770796e-19, 1.0687859854721439e-19, 1.0643273823243869e-19, 1.059849257293434e-19,
+ 1.055351199571202e-19, 1.0508327871578037e-19, 1.0462935864162494e-19, 1.0417331516046436e-19,
+ 1.0371510243844727e-19, 1.0325467333034829e-19, 1.0279197932515293e-19, 1.0232697048876598e-19,
+ 1.0185959540365581e-19, 1.013898011052333e-19, 1.009175330147477e-19, 1.0044273486846454e-19,
+ 9.996534864287244e-20, 9.948531447564429e-20, 9.900257058205621e-20, 9.851705316654313e-20,
+ 9.80286963290422e-20, 9.753743196574596e-20, 9.704318966385453e-20, 9.654589658987947e-20,
+ 9.60454773710132e-20, 9.554185396903316e-20, 9.503494554616229e-20, 9.452466832225325e-20,
+ 9.401093542260497e-20, 9.349365671565409e-20, 9.297273863971075e-20, 9.244808401782692e-20,
+ 9.191959185979496e-20, 9.13871571501726e-20, 9.085067062111788e-20, 9.03100185086906e-20,
+ 8.976508229113516e-20, 8.921573840749998e-20, 8.866185795476897e-20, 8.810330636147831e-20,
+ 8.753994303556269e-20, 8.697162098391639e-20, 8.639818640086038e-20, 8.581947822237302e-20,
+ 8.523532764256077e-20, 8.464555758841113e-20, 8.404998214837225e-20, 8.344840594973324e-20,
+ 8.2840623479122e-20, 8.222641833968076e-20, 8.160556243760346e-20, 8.097781508970379e-20,
+ 8.034292204250112e-20, 7.9700614391934e-20, 7.905060739119745e-20, 7.839259913230684e-20,
+ 7.772626908475868e-20, 7.705127647202012e-20, 7.636725846344508e-20, 7.567382815548135e-20,
+ 7.497057231156425e-20, 7.425704882472158e-20, 7.353278386042921e-20, 7.279726862938938e-20,
+ 7.204995573030996e-20, 7.12902549910028e-20, 7.051752872162244e-20, 6.97310862758892e-20,
+ 6.893017779370733e-20, 6.811398697040956e-20, 6.728162266220774e-20, 6.643210909198763e-20,
+ 6.556437436119487e-20, 6.467723689788537e-20, 6.376938937203267e-20, 6.28393794784348e-20,
+ 6.188558681299899e-20, 6.090619483242316e-20, 5.989915656489546e-20, 5.886215229253252e-20,
+ 5.779253679755271e-20, 5.668727286516658e-20, 5.554284642744753e-20, 5.435515678916088e-20,
+ 5.3119372426547794e-20, 5.182973825957843e-20, 5.047931295220812e-20, 4.9059602658819333e-20,
+ 4.756003683510097e-20, 4.5967194527575314e-20, 4.4263619567465964e-20, 4.242592320713738e-20,
+ 4.042157155716674e-20, 3.820304293025196e-20, 3.5696135223547374e-20, 3.277315994615917e-20,
+ 2.9176892376585344e-20, 2.4195231151204545e-20, 0.0};
+ /** Overhang table. Y_i = f(X_i). */
+ private static final double[] Y = {6.918899098832948e-23, 1.4202990535697683e-22, 2.1732316399259404e-22,
+ 2.9452908326033447e-22, 3.733322926509216e-22, 4.535231475217251e-22, 5.349509633185051e-22,
+ 6.175015744699501e-22, 7.01085131749555e-22, 7.856288599286739e-22, 8.710724705333867e-22,
+ 9.573651062292227e-22, 1.0444632219043918e-21, 1.1323290661676009e-21, 1.2209295628733119e-21,
+ 1.3102354679393653e-21, 1.4002207209079843e-21, 1.4908619375774252e-21, 1.582138006957303e-21,
+ 1.6740297667860313e-21, 1.7665197391694204e-21, 1.8595919128929468e-21, 1.9532315624377367e-21,
+ 2.0474250961975478e-21, 2.1421599281741028e-21, 2.2374243687320324e-21, 2.3332075309631245e-21,
+ 2.429499249937991e-21, 2.5262900126775297e-21, 2.6235708971028823e-21, 2.7213335185536967e-21,
+ 2.8195699827241005e-21, 2.9182728440709958e-21, 3.0174350689128386e-21, 3.1170500025683573e-21,
+ 3.217111339990819e-21, 3.3176130994398206e-21, 3.4185495988032995e-21, 3.5199154342406966e-21,
+ 3.621705460866417e-21, 3.723914775232861e-21, 3.8265386994058555e-21, 3.929572766453532e-21,
+ 4.03301270719345e-21, 4.1368544380629805e-21, 4.241094049995082e-21, 4.345727798196275e-21,
+ 4.450752092736164e-21, 4.5561634898686684e-21, 4.661958684014447e-21, 4.7681345003420505e-21,
+ 4.874687887892369e-21, 4.981615913197017e-21, 5.0889157543466486e-21, 5.196584695469838e-21,
+ 5.304620121587273e-21, 5.413019513809608e-21, 5.5217804448504855e-21, 5.630900574829082e-21,
+ 5.740377647338979e-21, 5.8502094857624066e-21, 5.9603939898108565e-21, 6.070929132274824e-21,
+ 6.181812955967001e-21, 6.2930435708446384e-21, 6.404619151298078e-21, 6.516537933593546e-21,
+ 6.628798213459353e-21, 6.741398343805535e-21, 6.85433673256781e-21, 6.967611840667461e-21,
+ 7.081222180079459e-21, 7.195166312001694e-21, 7.309442845118826e-21, 7.424050433954681e-21,
+ 7.538987777307655e-21, 7.65425361676395e-21, 7.769846735283895e-21, 7.885765955856934e-21,
+ 8.002010140221158e-21, 8.118578187643616e-21, 8.235469033757848e-21, 8.352681649455356e-21,
+ 8.47021503982796e-21, 8.58806824315818e-21, 8.706240329954993e-21, 8.824730402032477e-21,
+ 8.943537591629026e-21, 9.06266106056498e-21, 9.182099999436611e-21, 9.301853626844622e-21,
+ 9.421921188655315e-21, 9.542301957292816e-21, 9.662995231060764e-21, 9.784000333491997e-21,
+ 9.905316612724868e-21, 1.0026943440904879e-20, 1.0148880213610417e-20, 1.0271126349301457e-20,
+ 1.0393681288790118e-20, 1.0516544494732088e-20, 1.0639715451137926e-20, 1.076319366290336e-20,
+ 1.088697865535769e-20, 1.1011069973829531e-20, 1.1135467183229089e-20, 1.1260169867646259e-20,
+ 1.1385177629963887e-20, 1.1510490091485507e-20, 1.1636106891576963e-20, 1.176202768732133e-20,
+ 1.1888252153186578e-20, 1.2014779980705474e-20, 1.2141610878167194e-20, 1.2268744570320195e-20,
+ 1.2396180798085917e-20, 1.2523919318282839e-20, 1.2651959903360538e-20, 1.2780302341143342e-20,
+ 1.2908946434583201e-20, 1.3037892001521468e-20, 1.3167138874459203e-20, 1.3296686900335739e-20,
+ 1.342653594031518e-20, 1.3556685869580544e-20, 1.3687136577135297e-20, 1.3817887965612e-20,
+ 1.3948939951087837e-20, 1.4080292462906762e-20, 1.421194544350808e-20, 1.4343898848261192e-20,
+ 1.447615264530638e-20, 1.4608706815401313e-20, 1.474156135177323e-20, 1.4874716259976492e-20,
+ 1.5008171557755435e-20, 1.5141927274912272e-20, 1.527598345317996e-20, 1.5410340146099826e-20,
+ 1.554499741890387e-20, 1.5679955348401513e-20, 1.5815214022870783e-20, 1.5950773541953694e-20,
+ 1.6086634016555787e-20, 1.622279556874966e-20, 1.6359258331682407e-20, 1.649602244948686e-20,
+ 1.6633088077196497e-20, 1.6770455380664e-20, 1.690812453648326e-20, 1.7046095731914825e-20,
+ 1.7184369164814694e-20, 1.7322945043566328e-20, 1.7461823587015858e-20, 1.760100502441039e-20,
+ 1.77404895953393e-20, 1.7880277549678543e-20, 1.8020369147537807e-20, 1.8160764659210518e-20,
+ 1.8301464365126615e-20, 1.844246855580801e-20, 1.8583777531826755e-20, 1.872539160376576e-20,
+ 1.8867311092182093e-20, 1.900953632757279e-20, 1.91520676503431e-20, 1.9294905410777168e-20,
+ 1.9438049969011095e-20, 1.9581501695008306e-20, 1.9725260968537243e-20, 1.9869328179151295e-20,
+ 2.0013703726170975e-20, 2.015838801866827e-20, 2.030338147545316e-20, 2.0448684525062275e-20,
+ 2.0594297605749654e-20, 2.074022116547955e-20, 2.0886455661921353e-20, 2.1033001562446463e-20,
+ 2.1179859344127223e-20, 2.132702949373782e-20, 2.1474512507757144e-20, 2.1622308892373594e-20,
+ 2.177041916349182e-20, 2.191884384674137e-20, 2.2067583477487234e-20, 2.221663860084227e-20,
+ 2.2366009771681506e-20, 2.251569755465829e-20, 2.2665702524222297e-20, 2.2816025264639365e-20,
+ 2.2966666370013165e-20, 2.3117626444308697e-20, 2.326890610137758e-20, 2.342050596498518e-20,
+ 2.357242666883951e-20, 2.3724668856621966e-20, 2.387723318201982e-20, 2.4030120308760546e-20,
+ 2.4183330910647897e-20, 2.433686567159983e-20, 2.4490725285688176e-20, 2.464491045718012e-20,
+ 2.4799421900581494e-20, 2.4954260340681856e-20, 2.5109426512601375e-20, 2.5264921161839525e-20,
+ 2.5420745044325602e-20, 2.5576898926471056e-20, 2.5733383585223655e-20, 2.5890199808123478e-20,
+ 2.604734839336077e-20, 2.620483014983564e-20, 2.6362645897219624e-20, 2.6520796466019148e-20,
+ 2.667928269764085e-20, 2.6838105444458826e-20, 2.699726556988379e-20, 2.715676394843416e-20,
+ 2.731660146580911e-20, 2.747677901896354e-20, 2.7637297516185117e-20, 2.77981578771732e-20,
+ 2.795936103311988e-20, 2.812090792679301e-20, 2.8282799512621313e-20, 2.8445036756781554e-20,
+ 2.860762063728785e-20, 2.877055214408307e-20, 2.893383227913239e-20, 2.909746205651907e-20,
+ 2.9261442502542373e-20, 2.9425774655817774e-20, 2.9590459567379366e-20, 2.975549830078463e-20,
+ 2.992089193222143e-20, 3.0086641550617475e-20, 3.0252748257752036e-20, 3.041921316837019e-20,
+ 3.058603741029946e-20, 3.075322212456892e-20, 3.0920768465530904e-20, 3.108867760098517e-20,
+ 3.125695071230579e-20, 3.142558899457052e-20, 3.159459365669304e-20, 3.176396592155776e-20,
+ 3.193370702615749e-20, 3.210381822173386e-20, 3.227430077392068e-20, 3.244515596289013e-20,
+ 3.261638508350196e-20, 3.278798944545568e-20, 3.2959970373445826e-20, 3.313232920732032e-20,
+ 3.330506730224202e-20, 3.347818602885351e-20, 3.3651686773445136e-20, 3.382557093812645e-20,
+ 3.399983994100101e-20, 3.417449521634467e-20, 3.434953821478746e-20, 3.4524970403498974e-20,
+ 3.470079326637752e-20, 3.487700830424301e-20, 3.505361703503359e-20, 3.523062099400631e-20,
+ 3.540802173394162e-20, 3.558582082535201e-20, 3.576401985669479e-20, 3.5942620434589016e-20,
+ 3.612162418403681e-20, 3.630103274864904e-20, 3.6480847790875463e-20, 3.6661070992239485e-20,
+ 3.684170405357761e-20, 3.702274869528362e-20, 3.720420665755768e-20, 3.7386079700660407e-20,
+ 3.7568369605172066e-20, 3.7751078172256915e-20, 3.7934207223932926e-20, 3.811775860334692e-20,
+ 3.830173417505529e-20, 3.848613582531033e-20, 3.86709654623525e-20, 3.8856225016708545e-20,
+ 3.904191644149573e-20, 3.922804171273228e-20, 3.9414602829654225e-20, 3.960160181503872e-20,
+ 3.978904071553405e-20, 3.9976921601996467e-20, 4.016524656983399e-20, 4.035401773935739e-20,
+ 4.0543237256138495e-20, 4.0732907291375956e-20, 4.092303004226878e-20, 4.111360773239764e-20,
+ 4.1304642612114334e-20, 4.1496136958939466e-20, 4.1688093077968586e-20, 4.1880513302287083e-20,
+ 4.207339999339389e-20, 4.226675554163437e-20, 4.2460582366642555e-20, 4.265488291779298e-20,
+ 4.2849659674662346e-20, 4.3044915147501306e-20, 4.3240651877716606e-20, 4.343687243836386e-20,
+ 4.3633579434651235e-20, 4.383077550445433e-20, 4.402846331884258e-20, 4.4226645582617465e-20,
+ 4.44253250348628e-20, 4.4624504449507564e-20, 4.482418663590143e-20, 4.502437443940352e-20,
+ 4.522507074198459e-20, 4.5426278462843173e-20, 4.562800055903592e-20, 4.583024002612264e-20,
+ 4.603299989882643e-20, 4.6236283251709275e-20, 4.6440093199863635e-20, 4.66444328996204e-20,
+ 4.684930554927375e-20, 4.705471438982336e-20, 4.726066270573451e-20, 4.746715382571657e-20,
+ 4.7674191123520394e-20, 4.7881778018755285e-20, 4.8089917977726014e-20, 4.829861451429048e-20,
+ 4.8507871190738755e-20, 4.871769161869405e-20, 4.8928079460036324e-20, 4.913903842784919e-20,
+ 4.935057228739092e-20, 4.9562684857090195e-20, 4.977538000956748e-20, 4.9988661672682747e-20,
+ 5.0202533830610375e-20, 5.0417000524942233e-20, 5.0632065855819656e-20, 5.084773398309539e-20,
+ 5.106400912752639e-20, 5.1280895571998574e-20, 5.1498397662784496e-20, 5.1716519810835054e-20,
+ 5.1935266493106415e-20, 5.215464225392324e-20, 5.237465170637957e-20, 5.259529953377852e-20,
+ 5.281659049111218e-20, 5.303852940658309e-20, 5.326112118316879e-20, 5.348437080023076e-20,
+ 5.370828331516958e-20, 5.3932863865127733e-20, 5.4158117668741825e-20, 5.4384050027946e-20,
+ 5.461066632982836e-20, 5.483797204854241e-20, 5.506597274727535e-20, 5.529467408027557e-20,
+ 5.55240817949413e-20, 5.575420173397287e-20, 5.598503983759089e-20, 5.62166021458229e-20,
+ 5.644889480086096e-20, 5.668192404949321e-20, 5.691569624561198e-20, 5.715021785280148e-20,
+ 5.738549544700838e-20, 5.762153571929838e-20, 5.785834547870229e-20, 5.809593165515515e-20,
+ 5.833430130253229e-20, 5.857346160178616e-20, 5.881341986418809e-20, 5.905418353467947e-20,
+ 5.929576019533679e-20, 5.953815756895528e-20, 5.978138352275646e-20, 6.00254460722246e-20,
+ 6.02703533850779e-20, 6.051611378537999e-20, 6.076273575779827e-20, 6.101022795201527e-20,
+ 6.125859918729998e-20, 6.150785845724639e-20, 6.175801493468681e-20, 6.200907797678796e-20,
+ 6.226105713033821e-20, 6.251396213723503e-20, 6.276780294018204e-20, 6.30225896886053e-20,
+ 6.327833274479995e-20, 6.353504269031761e-20, 6.37927303326069e-20, 6.405140671191905e-20,
+ 6.431108310849226e-20, 6.457177105002818e-20, 6.483348231947592e-20, 6.509622896313888e-20,
+ 6.536002329912114e-20, 6.562487792613134e-20, 6.589080573266256e-20, 6.615781990656834e-20,
+ 6.642593394505607e-20, 6.669516166512051e-20, 6.696551721444132e-20, 6.723701508277054e-20,
+ 6.750967011383736e-20, 6.778349751779927e-20, 6.805851288427119e-20, 6.83347321959656e-20,
+ 6.861217184297964e-20, 6.889084863776731e-20, 6.917077983083762e-20, 6.945198312722278e-20,
+ 6.973447670376329e-20, 7.001827922726053e-20, 7.030340987355113e-20, 7.058988834756152e-20,
+ 7.087773490440541e-20, 7.11669703715918e-20, 7.145761617241673e-20, 7.174969435061705e-20,
+ 7.204322759637158e-20, 7.233823927374128e-20, 7.263475344964812e-20, 7.293279492450004e-20,
+ 7.323238926457911e-20, 7.353356283631946e-20, 7.383634284261274e-20, 7.414075736129108e-20,
+ 7.444683538595064e-20, 7.475460686929375e-20, 7.50641027691839e-20, 7.537535509762588e-20,
+ 7.568839697290355e-20, 7.600326267512978e-20, 7.631998770548812e-20, 7.663860884947315e-20,
+ 7.695916424446765e-20, 7.728169345202874e-20, 7.760623753529426e-20, 7.793283914196369e-20,
+ 7.826154259335684e-20, 7.859239398010826e-20, 7.892544126511772e-20, 7.926073439444657e-20,
+ 7.959832541692984e-20, 7.993826861336392e-20, 8.028062063623232e-20, 8.062544066104959e-20,
+ 8.097279055053708e-20, 8.132273503299865e-20, 8.167534189644072e-20, 8.20306822001853e-20,
+ 8.238883050596047e-20, 8.274986513072568e-20, 8.311386842380793e-20, 8.348092707129561e-20,
+ 8.385113243107135e-20, 8.422458090237601e-20, 8.460137433439796e-20, 8.498162047909447e-20,
+ 8.53654334942995e-20, 8.575293450418301e-20, 8.614425222533939e-20, 8.653952366824257e-20,
+ 8.693889492557206e-20, 8.734252206106456e-20, 8.775057211517437e-20, 8.816322424706147e-20,
+ 8.858067103642946e-20, 8.900311997372407e-20, 8.943079517345898e-20, 8.9863939353342e-20,
+ 9.030281613194174e-20, 9.074771271056305e-20, 9.119894302175006e-20, 9.165685144874882e-20,
+ 9.212181724922669e-20, 9.259425985526568e-20, 9.30746452740382e-20, 9.35634938854098e-20,
+ 9.406139003264672e-20, 9.45689939436514e-20, 9.50870567233135e-20, 9.56164394555198e-20,
+ 9.615813789991196e-20, 9.671331495418217e-20, 9.728334413500305e-20, 9.786986909344308e-20,
+ 9.847488715746005e-20, 9.910087013741517e-20, 9.975094533894022e-20, 1.004291788159128e-19,
+ 1.0114104330564085e-19, 1.0189424721829993e-19, 1.0270034796927329e-19, 1.0357834330014222e-19,
+ 1.0456455804293095e-19, 1.0575382882239675e-19, 1.0842021724855044e-19};
+
+ /** Underlying source of randomness. */
+ protected final UniformRandomProvider rng;
+ /** Exponential sampler used for the long tail. */
+ protected final ContinuousSampler exponential;
+
+ /**
+ * @param rng Generator of uniformly distributed random numbers.
+ */
+ ModifiedZigguratNormalizedGaussianSampler512(UniformRandomProvider rng) {
+ this.rng = rng;
+ exponential = new ModifiedZigguratExponentialSampler512(rng);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public double sample() {
+ final long xx = nextLong();
+ // Float multiplication squashes these last 9 bits, so they can be used to sample i
+ final int i = ((int) xx) & 0x1ff;
+
+ if (i < I_MAX) {
+ // Early exit.
+ // Branch frequency: 0.994145
+ return X[i] * xx;
+ }
+
+ // Recycle bits then advance RNG:
+ // u1 = RANDOM_INT63();
+ long u1 = xx & MAX_INT64;
+ // Another squashed, recyclable bit
+ // Use 2 - 1 or 0 - 1
+ final double signBit = ((u1 >>> 8) & 0x2) - 1.0;
+ final int j = normSampleA();
+ // Four kinds of overhangs:
+ // j = 0 : Sample from tail
+ // 0 < j < J_INFLECTION : Overhang is concave; only sample from Lower-Left triangle
+ // j = J_INFLECTION : Must sample from entire overhang rectangle
+ // j > J_INFLECTION : Overhangs are convex; implicitly accept point in Lower-Left triangle
+ //
+ // Conditional statements are arranged such that the more likely outcomes are first.
+ double x;
+ if (j > J_INFLECTION) {
+ // Convex overhang
+ // Branch frequency: 0.00442105
+ // Loop repeat frequency: 0.389804
+ for (;;) {
+ x = fastPrngSampleX(j, u1);
+ final long uDiff = randomInt63() - u1;
+ if (uDiff >= 0) {
+ // Lower-left triangle
+ break;
+ }
+ if (uDiff >= MAX_IE &&
+ // Within maximum distance of f(x) from the triangle hypotenuse.
+ // Long.MIN_VALUE is used as an unsigned int with value 2^63:
+ // uy = Long.MIN_VALUE - (ux + uDiff)
+ fastPrngSampleY(j, Long.MIN_VALUE - (u1 + uDiff)) < Math.exp(-0.5 * x * x)) {
+ break;
+ }
+ // uDiff < MAX_IE (upper-right triangle) or rejected as above the curve
+ u1 = randomInt63();
+ }
+ } else if (j < J_INFLECTION) {
+ if (j == 0) {
+ // Tail
+ // Branch frequency: 0.000124818
+ // Note: Although less frequent than the next branch, j == 0 is a subset of
+ // j < J_INFLECTION and must be first.
+ do {
+ x = ONE_OVER_X_0 * exponential.sample();
+ } while (exponential.sample() < 0.5 * x * x);
+ x += X_0;
+ } else {
+ // Concave overhang
+ // Branch frequency: 0.00130516
+ for (;;) {
+ // U_x <- min(U_1, U_2)
+ // distance <- | U_1 - U_2 |
+ // U_y <- 1 - (U_x + distance)
+ long uDiff = randomInt63() - u1;
+ if (uDiff < 0) {
+ uDiff = -uDiff;
+ u1 -= uDiff;
+ }
+ x = fastPrngSampleX(j, u1);
+ if (uDiff > MIN_IE ||
+ fastPrngSampleY(j, Long.MIN_VALUE - (u1 + uDiff)) < Math.exp(-0.5 * x * x)) {
+ break;
+ }
+ u1 = randomInt63();
+ }
+ }
+ } else {
+ // Inflection point
+ // Branch frequency: 0.00000402238
+ for (;;) {
+ x = fastPrngSampleX(j, u1);
+ if (fastPrngSampleY(j, randomInt63()) < Math.exp(-0.5 * x * x)) {
+ break;
+ }
+ u1 = randomInt63();
+ }
+ }
+ return signBit * x;
+ }
+
+ /**
+ * Alias sampling.
+ * See http://scorevoting.net/WarrenSmithPages/homepage/sampling.abs
+ *
+ * @return the alias
+ */
+ protected int normSampleA() {
+ final long x = nextLong();
+ // j <- I(0, 512)
+ final int j = ((int) x) & 0x1ff;
+ return x >= IPMF[j] ? MAP[j] : j;
+ }
+
+ /**
+ * Generates a {@code long}.
+ *
+ * @return the long
+ */
+ protected long nextLong() {
+ return rng.nextLong();
+ }
+
+ /**
+ * Return a positive long in {@code [0, 2^63)}.
+ *
+ * @return the long
+ */
+ protected long randomInt63() {
+ return rng.nextLong() & MAX_INT64;
+ }
+
+ /**
+ * Auxilary function to see if rejection sampling is required in the overhang.
+ * See Fig. 2 in the main text.
+ *
+ * @param j j
+ * @param ux ux
+ * @return the sample
+ */
+ protected static double fastPrngSampleX(int j, long ux) {
+ return X[j] * TWO_POW_63 + (X[j - 1] - X[j]) * ux;
+ }
+
+ /**
+ * Auxilary function to see if rejection sampling is required in the overhang.
+ * See Fig. 2 in the main text.
+ *
+ * @param i i
+ * @param uy uy
+ * @return the sample
+ */
+ protected static double fastPrngSampleY(int i, long uy) {
+ return Y[i - 1] * TWO_POW_63 + (Y[i] - Y[i - 1]) * uy;
+ }
+ }
+
+ /**
* Modified Ziggurat method for sampling from an exponential distribution.
*
* <p>Uses the algorithm from:
@@ -2268,6 +2876,574 @@ public class ZigguratSamplerPerformance {
}
/**
+ * Modified Ziggurat method for sampling from an exponential distribution.
+ *
+ * <p>Uses the algorithm from McFarland, C.D. (2016).
+ *
+ * <p>This is a copy of {@link ModifiedZigguratExponentialSampler} using
+ * a table size of 512.
+ */
+ static class ModifiedZigguratExponentialSampler512 implements ContinuousSampler {
+ /** Maximum i value for early exit. */
+ protected static final int I_MAX = 508;
+ /** Maximum distance value for early exit. */
+ protected static final long IE_MAX = 507874389497522840L;
+ /** Beginning of tail. */
+ protected static final double X_0 = 8.362025281328359;
+
+ /** The alias map. */
+ private static final int[] MAP = {0, 0, 1, 473, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 508, 508, 508, 508,
+ 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508,
+ 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508,
+ 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508,
+ 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508,
+ 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508,
+ 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508,
+ 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508,
+ 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508,
+ 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508,
+ 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508,
+ 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508,
+ 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508,
+ 508, 508, 508, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507,
+ 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 506, 506, 506, 506, 506, 506, 506, 506, 506, 506,
+ 506, 506, 506, 506, 506, 506, 506, 505, 505, 505, 505, 505, 505, 505, 505, 505, 505, 505, 504, 504, 504,
+ 504, 504, 504, 504, 504, 504, 503, 503, 503, 503, 503, 503, 503, 503, 502, 502, 502, 502, 502, 502, 501,
+ 501, 501, 501, 501, 500, 500, 500, 500, 500, 499, 499, 499, 499, 498, 498, 498, 498, 497, 497, 497, 496,
+ 496, 496, 495, 495, 495, 494, 494, 493, 493, 492, 492, 491, 491, 490, 490, 489, 489, 488, 487, 486, 485,
+ 485, 484, 482, 481, 479, 477, 3, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 8, 9, 9, 10, 13, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 474, 475, 476, 477, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490,
+ 491, 492, 493, 494, 495, 496, 497, 498, 499, 500, 501, 502, 503, 504, 505, 506, 507, 508, 2, 0, 0, 0};
+ /** The alias inverse PMF. */
+ private static final long[] IPMF = {9223372036854775296L, 2636146522269100032L, 3561072052814771200L,
+ 3481882573634022912L, 7116525960784167936L, 3356999026233157120L, 4185343482988790272L,
+ 7712945794725800960L, 7827282421678200832L, 5031524219672503296L, 8479703117927504896L,
+ 8798557826262976512L, 6461753601163497984L, 5374576640182409216L, 8285209933846173696L,
+ 7451775918468278784L, 6710527725555065344L, 6046590166603477504L, 5448165515863960576L,
+ 4905771306157685248L, 4411694943948817408L, 3959596233157434880L, 3544212893101320192L,
+ 3161139128795137536L, 2806656884941820416L, 2477605671376185344L, 2171281018524273664L,
+ 1885354452557434880L, 1617809833614047744L, 1366892269237658112L, 1131066787615028736L, 908984654997058560L,
+ 699455731348318720L, 501425633583915520L, 313956755007992832L, 136212399366961152L, -32556553021349888L,
+ -193022908001625600L, -345792716399554560L, -491413423379838464L, -630380845888988672L,
+ -763145170929260544L, -890116131912690176L, -1011667492054083072L, -1128140941080192000L,
+ -1239849493252469760L, -1347080459893031424L, -1450098057542626304L, -1549145703018891776L,
+ -1644448038535791104L, -1736212723361025536L, -1824632022940825600L, -1909884221816344064L,
+ -1992134882804800512L, -2071537971688286208L, -2148236863947458560L, -2222365247780633088L,
+ -2294047935714820096L, -2363401595468253696L, -2430535409323403776L, -2495551670069566976L,
+ -2558546320552583680L, -2619609442985608192L, -2678825703417424896L, -2736274756101145600L,
+ -2792031611938902016L, -2846166974686572544L, -2898747548177031680L, -2949836317447342592L,
+ -2999492806329770496L, -3047773313785532928L, -3094731131006235648L, -3140416741094473728L,
+ -3184878002938374144L, -3228160320727380992L, -3270306800406949376L, -3311358394234071552L,
+ -3351354034484032512L, -3390330757247591424L, -3428323817169865728L, -3465366793898720256L,
+ -3501491690934902784L, -3536729027513080832L, -3571107924081618944L, -3604656181899062784L,
+ -3637400357214628352L, -3669365830461451264L, -3700576870849548288L, -3731056696714091520L,
+ -3760827531940795392L, -3789910658766305792L, -3818326467220366848L, -3846094501460680704L,
+ -3873233503224223232L, -3899761452604410880L, -3925695606345008640L, -3951052533825223680L,
+ -3975848150898364416L, -4000097751731727360L, -4023816038786208256L, -4047017151058499584L,
+ -4069714690707166208L, -4091921748165281792L, -4113650925843118592L, -4134914360510158336L,
+ -4155723744443228160L, -4176090345419594752L, -4196025025626374656L, -4215538259557954560L,
+ -4234640150960326144L, -4253340448884000768L, -4271648562898405376L, -4289573577519592448L,
+ -4307124265897231872L, -4324309102806436352L, -4341136276983992320L, -4357613702847894016L,
+ -4373749031636836352L, -4389549662001094144L, -4405022750077366784L, -4420175219077067264L,
+ -4435013768413905920L, -4449544882397231104L, -4463774838515782144L, -4477709715332459008L,
+ -4491355400012626944L, -4504717595505328640L, -4517801827395838976L, -4530613450446389760L,
+ -4543157654842793472L, -4555439472160934400L, -4567463781068195840L, -4579235312773997568L,
+ -4590758656240654848L, -4602038263168300032L, -4613078452764409856L, -4623883416308989952L,
+ -4634457221524290048L, -4644803816761235456L, -4654927035008246784L, -4664830597734270976L,
+ -4674518118570737664L, -4683993106843208704L, -4693258970957511168L, -4702319021648195072L,
+ -4711176475095642112L, -4719834455917983232L, -4728296000042890240L, -4736564057465815040L,
+ -4744641494898972160L, -4752531098316131328L, -4760235575398025216L, -4767757557883156992L,
+ -4775099603826595840L, -4782264199773566464L, -4789253762848160256L, -4796070642763833856L,
+ -4802717123757088768L, -4809195426448159744L, -4815507709632380416L, -4821656072004040192L,
+ -4827642553816744448L, -4833469138481454080L, -4839137754106220032L, -4844650274978936320L,
+ -4850008522996425728L, -4855214269039884288L, -4860269234302464000L, -4865175091566906368L,
+ -4869933466437730816L, -4874545938529117696L, -4879014042609741312L, -4883339269707099136L,
+ -4887523068171446784L, -4891566844702813184L, -4895471965340231168L, -4899239756417071616L,
+ -4902871505481196544L, -4906368462183164928L, -4909731839132712448L, -4912962812724644864L,
+ -4916062523935916544L, -4919032079093866496L, -4921872550617327616L, -4924584977732045824L,
+ -4927170367159303168L, -4929629693781258752L, -4931963901281752576L, -4934173902764700160L,
+ -4936260581349647360L, -4938224790746291200L, -4940067355807971840L, -4941789073065357824L,
+ -4943390711239933952L, -4944873011739753984L, -4946236689135308800L, -4947482431619080192L,
+ -4948610901446864896L, -4949622735363246080L, -4950518545009749504L, -4951298917317924864L,
+ -4951964414887600640L, -4952515576348487168L, -4952952916709260288L, -4953276927691216384L,
+ -4953488078048885760L, -4953586813876376064L, -4953573558902138368L, -4953448714769485312L,
+ -4953212661305179136L, -4952865756776645632L, -4952408338136501760L, -4951840721255068672L,
+ -4951163201143173120L, -4950376052162316800L, -4949479528224847360L, -4948473862982736384L,
+ -4947359270007034368L, -4946135942956237312L, -4944804055734229504L, -4943363762640024064L,
+ -4941815198506020352L, -4940158478827333120L, -4938393699882143232L, -4936520938842464768L,
+ -4934540253875459072L, -4932451684236201472L, -4930255250350992896L, -4927950953893274112L,
+ -4925538777848453632L, -4923018686572188672L, -4920390625839525888L, -4917654522885157888L,
+ -4914810286435288576L, -4911857806732278272L, -4908796955549192192L, -4905627586197715456L,
+ -4902349533527011840L, -4898962613914057216L, -4895466625247106560L, -4891861346899963904L,
+ -4888146539697684992L, -4884321945875628032L, -4880387289029549568L, -4876342274056310272L,
+ -4872186587089345536L, -4867919895422610944L, -4863541847428798464L, -4859052072467801600L,
+ -4854450180787865088L, -4849735763417182208L, -4844908392047856128L, -4839967618911950848L,
+ -4834912976647099392L, -4829743978155096576L, -4824460116451147776L, -4819060864504044544L,
+ -4813545675067768320L, -4807913980504056832L, -4802165192594749952L, -4796298702346892288L,
+ -4790313879785735168L, -4784210073740736512L, -4777986611619728896L, -4771642799174403072L,
+ -4765177920255393792L, -4758591236556836352L, -4751881987350666752L, -4745049389210733568L,
+ -4738092635724898304L, -4731010897197732864L, -4723803320339894784L, -4716469027948174336L,
+ -4709007118571786240L, -4701416666168034304L, -4693696719744952320L, -4685846302991571968L,
+ -4677864413895422464L, -4669750024346546688L, -4661502079728433664L, -4653119498494611968L,
+ -4644601171731585024L, -4635945962706888192L, -4627152706402486784L, -4618220209032402944L,
+ -4609147247545243136L, -4599932569110216704L, -4590574890586744832L, -4581072897977050112L,
+ -4571425245860782592L, -4561630556812469760L, -4551687420800102912L, -4541594394564215808L,
+ -4531350000978089984L, -4520952728387175936L, -4510401029928645120L, -4499693322828163584L,
+ -4488827987675754496L, -4477803367678713856L, -4466617767890585600L, -4455269454416637440L,
+ -4443756653594040832L, -4432077551146284544L, -4420230291311382528L, -4408212975942271488L,
+ -4396023663579625472L, -4383660368494419456L, -4371121059701586432L, -4358403659940780544L,
+ -4345506044627643904L, -4332426040768207872L, -4319161425842345472L, -4305709926649207296L,
+ -4292069218116598784L, -4278236922073029120L, -4264210605978586624L, -4249987781616803840L,
+ -4235565903742823424L, -4220942368688843264L, -4206114512923164672L, -4191079611563289088L,
+ -4175834876839676928L, -4160377456508627456L, -4144704432214183936L, -4128812817794444800L,
+ -4112699557531435520L, -4096361524344448000L, -4079795517919899648L, -4062998262780994048L,
+ -4045966406289958912L, -4028696516583542784L, -4011185080437596160L, -3993428501058901504L,
+ -3975423095799736320L, -3957165093794900480L, -3938650633514732032L, -3919875760234452992L,
+ -3900836423412657152L, -3881528473978691584L, -3861947661522247168L, -3842089631384604160L,
+ -3821949921642690048L, -3801523959987316736L, -3780807060485497856L, -3759794420226106880L,
+ -3738481115842412032L, -3716862099905139200L, -3694932197183221248L, -3672686100763535872L,
+ -3650118368025705472L, -3627223416464823808L, -3603995519354882048L, -3580428801247209472L,
+ -3556517233294936064L, -3532254628397208576L, -3507634636153634816L, -3482650737621700608L,
+ -3457296239866780160L, -3431564270296417792L, -3405447770767880704L, -3378939491458745856L,
+ -3352031984490172416L, -3324717597289475072L, -3296988465680861184L, -3268836506691269120L,
+ -3240253411056924672L, -3211230635415641088L, -3181759394171538432L, -3151830651013152256L,
+ -3121435110069826048L, -3090563206687621632L, -3059205097804578816L, -3027350651907195904L,
+ -2994989438544094720L, -2962110717375283712L, -2928703426733917184L, -2894756171672258048L,
+ -2860257211467748352L, -2825194446557172224L, -2789555404872457216L, -2753327227540304896L,
+ -2716496653917054464L, -2679050005916396544L, -2640973171596317184L, -2602251587958849024L,
+ -2562870222922691584L, -2522813556418801152L, -2482065560560435712L, -2440609678833421312L,
+ -2398428804250509824L, -2355505256407986688L, -2311820757381316608L, -2267356406388873216L,
+ -2222092653150109696L, -2176009269860336640L, -2129085321695611904L, -2081299135757883392L,
+ -2032628268363105280L, -1983049470568565760L, -1932538651826487296L, -1881070841645808640L,
+ -1828620149131529728L, -1775159720264906752L, -1720661692774047744L, -1665097148437127680L,
+ -1608436062642298880L, -1550647251022831104L, -1491698312963664384L, -1431555571764694528L,
+ -1370184011228092416L, -1307547208415545344L, -1243607262304812544L, -1178324718048254976L,
+ -1111658486516102144L, -1043565758774211584L, -974001915124345856L, -902920428295306752L,
+ -830272760342546432L, -756008252773183488L, -680074009369660928L, -602414771142033408L,
+ -522972782779506176L, -441687649923274752L, -358496186511785984L, -273332251384862720L,
+ -186126573250838016L, -96806563039876096L, -5296112566262784L, 88484621680143872L, 184619450912608768L,
+ 283196404027497984L, 384307996761360384L, 488051521767595008L, 594529361535797760L, 703849326283634688L,
+ 816125019179379200L, 931476231515671552L, 1050029370739642368L, 1171917924579436544L, 1297282964870890496L,
+ 1426273695110094848L, 1559048046230309888L, 1695773325638197760L, 1836626925155011584L,
+ 1981797094206053888L, 2131483785391109632L, 2285899580478475776L, 2445270705902480384L,
+ 2609838148036959744L, 2779858879886981120L, 2955607212425994240L, 3137376285625809920L,
+ 3325479716351016448L, 3520253422737882112L, 3722057647546029568L, 3931279206301515776L,
+ 4148333989964127232L, 4373669756431084544L, 4607769250590803968L, 4851153699010013696L,
+ 5104386732888089088L, 5368078801878179840L, 5642892152071508992L, 5929546454235676672L,
+ 6228825183767088640L, 6541582872345928704L, 6868753373709051392L, 7211359313221728768L,
+ 7570522924211155456L, 7947478514849258496L, 8343586859683210240L, 8760351872223335936L,
+ 9199439992591985152L, 3921213358161086464L, 4850044974529517568L, 6296921656268977664L,
+ 8292973759562619904L, 3075143244722959872L, 6274953360832545280L, 2210268915646535680L,
+ 6778561557392493568L, 4052431235721115136L, 2017158148825034240L, 9030121550070927872L,
+ 8695700292397356032L, 749256839723897344L, 2212185722591297024L, 4780810392134832640L, 8573064486620626432L,
+ 4685427019526152192L, 2026848442171050496L, 795427058175291392L, 1220057396927800832L, 3568726050706383360L,
+ 8159594562977490432L, 5249819115171273728L, 5086123243830243840L, 8282283418103647744L,
+ 4836310890809390080L, 6126145310249794560L, 2267629071146367488L, 5974727006028887552L,
+ 8264939763687273472L, 608340989510339584L, 828635949469412864L, 8856898102852928512L, 1720475810403128832L,
+ 3683415679219046400L, -1284830592014387712L, -9223372036854775808L, -9223372036854775808L,
+ -9223372036854775808L};
+ /**
+ * The precomputed ziggurat lengths, denoted X_i in the main text. X_i = length of
+ * ziggurat layer i.
+ */
+ private static final double[] X = {9.066125976394918e-19, 8.263176964596684e-19, 7.784282104206918e-19,
+ 7.440138137244747e-19, 7.170634551247567e-19, 6.948734962698102e-19, 6.759905994143853e-19,
+ 6.595417386676109e-19, 6.44960764869756e-19, 6.318593172398609e-19, 6.199592614043609e-19,
+ 6.090544855608598e-19, 5.989879531319532e-19, 5.896372336649496e-19, 5.809050077944015e-19,
+ 5.727126242519077e-19, 5.649956016143745e-19, 5.577004098080976e-19, 5.507821175595968e-19,
+ 5.442026402205546e-19, 5.379294128626943e-19, 5.319343704005985e-19, 5.261931531836978e-19,
+ 5.206844807204844e-19, 5.153896525288391e-19, 5.102921463263689e-19, 5.0537729161623905e-19,
+ 5.006320022905563e-19, 4.960445558817678e-19, 4.916044100170685e-19, 4.873020487905351e-19,
+ 4.831288533806017e-19, 4.790769924576001e-19, 4.7513932885346785e-19, 4.713093396787531e-19,
+ 4.675810476249156e-19, 4.639489616220167e-19, 4.604080253621108e-19, 4.569535724684215e-19,
+ 4.535812873056953e-19, 4.502871706000609e-19, 4.470675091764292e-19, 4.43918849234975e-19,
+ 4.408379726809414e-19, 4.378218760981047e-19, 4.348677520190027e-19, 4.3197297219702936e-19,
+ 4.2913507262878116e-19, 4.263517401111986e-19, 4.236208001483923e-19, 4.209402060485899e-19,
+ 4.1830802907323973e-19, 4.1572244951862374e-19, 4.1318174862592063e-19, 4.106843012289693e-19,
+ 4.0822856906037985e-19, 4.058130946464292e-19, 4.0343649572961074e-19, 4.0109746016499096e-19,
+ 3.987947412428338e-19, 3.965271533954313e-19, 3.942935682508446e-19, 3.920929110004198e-19,
+ 3.8992415705058057e-19, 3.877863289325851e-19, 3.856784934467374e-19, 3.8359975902000546e-19,
+ 3.8154927325817224e-19, 3.795262206755667e-19, 3.7752982058712154e-19, 3.7555932514901226e-19,
+ 3.7361401753547253e-19, 3.7169321024057316e-19, 3.69796243494815e-19, 3.6792248378733595e-19,
+ 3.6607132248538204e-19, 3.6424217454345153e-19, 3.6243447729520606e-19, 3.6064768932185395e-19,
+ 3.5888128939126416e-19, 3.571347754625651e-19, 3.554076637514328e-19, 3.5369948785167605e-19,
+ 3.520097979090946e-19, 3.5033815984391743e-19, 3.4868415461842876e-19, 3.470473775466644e-19,
+ 3.454274376433074e-19, 3.438239570091394e-19, 3.4223657025060954e-19, 3.4066492393126986e-19,
+ 3.3910867605299972e-19, 3.375674955650951e-19, 3.36041061899445e-19, 3.3452906453014644e-19,
+ 3.330312025560311e-19, 3.3154718430468554e-19, 3.300767269566494e-19, 3.2861955618856956e-19,
+ 3.2717540583417136e-19, 3.2574401756198997e-19, 3.2432514056887605e-19, 3.2291853128835623e-19,
+ 3.2152395311299247e-19, 3.2014117612994074e-19, 3.1876997686896117e-19, 3.1741013806218296e-19,
+ 3.1606144841497054e-19, 3.147237023872807e-19, 3.133966999849381e-19, 3.120802465602945e-19,
+ 3.107741526217679e-19, 3.094782336517918e-19, 3.081923099327311e-19, 3.069162063803502e-19,
+ 3.056497523844424e-19, 3.0439278165625384e-19, 3.0314513208235683e-19, 3.0190664558464783e-19,
+ 3.006771679861636e-19, 2.994565488824278e-19, 2.982446415180565e-19, 2.97041302668365e-19,
+ 2.9584639252573667e-19, 2.946597745905224e-19, 2.9348131556625803e-19, 2.923108852589938e-19,
+ 2.9114835648054477e-19, 2.899936049554792e-19, 2.888465092316728e-19, 2.8770695059426596e-19,
+ 2.865748129828689e-19, 2.8544998291186936e-19, 2.843323493937027e-19, 2.8322180386495424e-19,
+ 2.8211824011516853e-19, 2.810215542182466e-19, 2.7993164446631984e-19, 2.788484113059931e-19,
+ 2.7777175727685546e-19, 2.767015869521629e-19, 2.756378068816009e-19, 2.745803255360393e-19,
+ 2.7352905325419784e-19, 2.724839021911418e-19, 2.7144478626853394e-19, 2.7041162112657045e-19,
+ 2.6938432407753285e-19, 2.683628140608911e-19, 2.673470115998956e-19, 2.663368387595991e-19,
+ 2.653322191062523e-19, 2.6433307766801955e-19, 2.6333934089696193e-19, 2.623509366322412e-19,
+ 2.6136779406449473e-19, 2.603898437013396e-19, 2.5941701733396064e-19, 2.5844924800474283e-19,
+ 2.574864699759092e-19, 2.565286186991254e-19, 2.5557563078603673e-19, 2.546274439797022e-19,
+ 2.5368399712689353e-19, 2.5274523015122715e-19, 2.5181108402709945e-19, 2.508815007543965e-19,
+ 2.499564233339501e-19, 2.4903579574371396e-19, 2.481195629156353e-19, 2.472076707131958e-19,
+ 2.4630006590960037e-19, 2.4539669616659003e-19, 2.4449751001385796e-19, 2.4360245682904773e-19,
+ 2.427114868183142e-19, 2.418245509974277e-19, 2.4094160117340305e-19, 2.4006258992663645e-19,
+ 2.391874705935326e-19, 2.3831619724960594e-19, 2.3744872469304068e-19, 2.3658500842869427e-19,
+ 2.357250046525298e-19, 2.3486867023646363e-19, 2.340159627136144e-19, 2.3316684026394113e-19,
+ 2.3232126170025724e-19, 2.3147918645460906e-19, 2.3064057456500724e-19, 2.298053866624993e-19,
+ 2.289735839585738e-19, 2.2814512823288434e-19, 2.2731998182128476e-19, 2.264981076041651e-19,
+ 2.2567946899507905e-19, 2.248640299296549e-19, 2.240517548547797e-19, 2.232426087180504e-19,
+ 2.2243655695748146e-19, 2.2163356549146385e-19, 2.2083360070896563e-19, 2.2003662945996843e-19,
+ 2.192426190461318e-19, 2.1845153721167946e-19, 2.176633521345008e-19, 2.1687803241746032e-19,
+ 2.1609554707991062e-19, 2.153158655494016e-19, 2.145389576535809e-19, 2.1376479361227967e-19,
+ 2.1299334402977885e-19, 2.1222457988725017e-19, 2.1145847253536737e-19, 2.1069499368708242e-19,
+ 2.0993411541056253e-19, 2.0917581012228278e-19, 2.0842005058027066e-19, 2.076668098774977e-19,
+ 2.0691606143541438e-19, 2.061677789976242e-19, 2.0542193662369327e-19, 2.0467850868309113e-19,
+ 2.039374698492599e-19, 2.031987950938075e-19, 2.0246245968082214e-19, 2.0172843916130424e-19,
+ 2.0099670936771298e-19, 2.0026724640862402e-19, 1.9954002666349563e-19, 1.9881502677754006e-19,
+ 1.9809222365669745e-19, 1.9737159446270942e-19, 1.966531166082896e-19, 1.959367677523886e-19,
+ 1.9522252579555087e-19, 1.9451036887536058e-19, 1.9380027536197503e-19, 1.9309222385374197e-19,
+ 1.9238619317289982e-19, 1.9168216236135756e-19, 1.9098011067655294e-19, 1.9028001758738615e-19,
+ 1.8958186277022764e-19, 1.8888562610499751e-19, 1.88191287671315e-19, 1.874988277447156e-19,
+ 1.8680822679293485e-19, 1.8611946547225595e-19, 1.8543252462392036e-19, 1.8474738527059914e-19,
+ 1.840640286129235e-19, 1.833824360260732e-19, 1.8270258905642057e-19, 1.820244694182295e-19,
+ 1.8134805899040715e-19, 1.8067333981330703e-19, 1.8000029408558255e-19, 1.793289041610889e-19,
+ 1.786591525458323e-19, 1.779910218949653e-19, 1.773244950098264e-19, 1.7665955483502355e-19,
+ 1.75996184455559e-19, 1.7533436709399558e-19, 1.7467408610766236e-19, 1.7401532498589862e-19,
+ 1.7335806734733532e-19, 1.727022969372126e-19, 1.7204799762473213e-19, 1.7139515340044364e-19,
+ 1.70743748373664e-19, 1.7009376676992816e-19, 1.694451929284709e-19, 1.6879801129973803e-19,
+ 1.6815220644292632e-19, 1.6750776302355125e-19, 1.6686466581104123e-19, 1.6622289967635762e-19,
+ 1.655824495896394e-19, 1.6494330061787188e-19, 1.64305437922578e-19, 1.6366884675753161e-19,
+ 1.6303351246649206e-19, 1.6239942048095857e-19, 1.61766556317944e-19, 1.6113490557776692e-19,
+ 1.6050445394186123e-19, 1.598751871706023e-19, 1.5924709110114872e-19, 1.5862015164529922e-19,
+ 1.5799435478736328e-19, 1.5736968658204502e-19, 1.5674613315233954e-19, 1.561236806874404e-19,
+ 1.55502315440658e-19, 1.5488202372734756e-19, 1.5426279192284608e-19, 1.536446064604174e-19,
+ 1.5302745382920442e-19, 1.5241132057218782e-19, 1.5179619328415014e-19, 1.5118205860964477e-19,
+ 1.505689032409686e-19, 1.4995671391613777e-19, 1.4934547741686533e-19, 1.4873518056654034e-19,
+ 1.4812581022820734e-19, 1.47517353302545e-19, 1.4690979672584366e-19, 1.4630312746798053e-19,
+ 1.456973325303913e-19, 1.4509239894403808e-19, 1.444883137673718e-19, 1.438850640842889e-19,
+ 1.4328263700208072e-19, 1.4268101964937506e-19, 1.4208019917406874e-19, 1.4148016274125018e-19,
+ 1.4088089753111074e-19, 1.4028239073684423e-19, 1.396846295625332e-19, 1.3908760122102091e-19,
+ 1.3849129293176794e-19, 1.3789569191869245e-19, 1.3730078540799268e-19, 1.3670656062595043e-19,
+ 1.361130047967149e-19, 1.3552010514006475e-19, 1.3492784886914775e-19, 1.343362231881967e-19,
+ 1.337452152902197e-19, 1.3315481235466403e-19, 1.3256500154505191e-19, 1.3197577000658667e-19,
+ 1.3138710486372786e-19, 1.3079899321773381e-19, 1.3021142214417001e-19, 1.296243786903814e-19,
+ 1.2903784987292747e-19, 1.2845182267497766e-19, 1.2786628404366604e-19, 1.2728122088740255e-19,
+ 1.2669662007313963e-19, 1.2611246842359178e-19, 1.2552875271440607e-19, 1.2494545967128163e-19,
+ 1.2436257596703557e-19, 1.2378008821861334e-19, 1.231979829840411e-19, 1.2261624675931726e-19,
+ 1.2203486597524123e-19, 1.2145382699417624e-19, 1.2087311610674357e-19, 1.2029271952844551e-19,
+ 1.1971262339621383e-19, 1.1913281376488073e-19, 1.1855327660356906e-19, 1.1797399779199848e-19,
+ 1.1739496311670397e-19, 1.1681615826716313e-19, 1.1623756883182844e-19, 1.1565918029406041e-19,
+ 1.1508097802795774e-19, 1.1450294729408e-19, 1.1392507323505832e-19, 1.133473408710896e-19,
+ 1.1276973509530898e-19, 1.1219224066903596e-19, 1.1161484221688824e-19, 1.1103752422175824e-19,
+ 1.1046027101964606e-19, 1.0988306679434292e-19, 1.0930589557195864e-19, 1.0872874121528646e-19,
+ 1.0815158741799823e-19, 1.0757441769866241e-19, 1.0699721539457744e-19, 1.0641996365541205e-19,
+ 1.0584264543664434e-19, 1.0526524349279041e-19, 1.0468774037041343e-19, 1.0411011840090299e-19,
+ 1.0353235969301472e-19, 1.0295444612515902e-19, 1.0237635933742761e-19, 1.0179808072334579e-19,
+ 1.0121959142133761e-19, 1.0064087230589085e-19, 1.0006190397840746e-19, 9.948266675772465e-20,
+ 9.890314067029116e-20, 9.832330543998192e-20, 9.77431404775337e-20, 9.716262486958349e-20,
+ 9.658173736728982e-20, 9.600045637451667e-20, 9.541875993555806e-20, 9.483662572238009e-20,
+ 9.425403102135636e-20, 9.36709527194705e-20, 9.308736728995855e-20, 9.250325077736202e-20,
+ 9.191857878196082e-20, 9.133332644355302e-20, 9.074746842454686e-20, 9.016097889232776e-20,
+ 8.957383150086088e-20, 8.898599937148752e-20, 8.83974550728703e-20, 8.780817060003978e-20,
+ 8.721811735249173e-20, 8.662726611128059e-20, 8.603558701505162e-20, 8.544304953494964e-20,
+ 8.484962244833846e-20, 8.425527381126013e-20, 8.365997092955832e-20, 8.306368032858488e-20,
+ 8.246636772140225e-20, 8.186799797538864e-20, 8.126853507714563e-20, 8.066794209560029e-20,
+ 8.006618114318622e-20, 7.946321333497837e-20, 7.885899874564743e-20, 7.825349636408865e-20,
+ 7.764666404556869e-20, 7.703845846122129e-20, 7.642883504470902e-20, 7.58177479358532e-20,
+ 7.520514992101743e-20, 7.459099237001235e-20, 7.397522516926911e-20, 7.335779665100703e-20,
+ 7.273865351809722e-20, 7.211774076429659e-20, 7.149500158949814e-20, 7.087037730961018e-20,
+ 7.024380726064147e-20, 6.96152286965294e-20, 6.89845766802037e-20, 6.835178396732923e-20,
+ 6.771678088211617e-20, 6.707949518452485e-20, 6.64398519281239e-20, 6.579777330778369e-20,
+ 6.515317849630154e-20, 6.450598346895782e-20, 6.385610081489444e-20, 6.320343953408397e-20,
+ 6.254790481851989e-20, 6.188939781610152e-20, 6.122781537550966e-20, 6.056304977016756e-20,
+ 5.989498839915096e-20, 5.922351346264923e-20, 5.854850160927849e-20, 5.786982355220268e-20,
+ 5.718734365062205e-20, 5.650091945273011e-20, 5.581040119571103e-20, 5.511563125773486e-20,
+ 5.441644355619287e-20, 5.3712662885580816e-20, 5.3004104187460606e-20, 5.2290571743781936e-20,
+ 5.157185828349097e-20, 5.084774399074948e-20, 5.011799540118182e-20, 4.9382364170293304e-20,
+ 4.8640585695477616e-20, 4.789237756975016e-20, 4.7137437841375266e-20, 4.637544304873078e-20,
+ 4.5606045993857614e-20, 4.482887321089667e-20, 4.40435220766595e-20, 4.324955749943926e-20,
+ 4.2446508108220653e-20, 4.163386184685984e-20, 4.081106085546285e-20, 3.997749549257881e-20,
+ 3.9132497314870153e-20, 3.827533078275297e-20, 3.740518339709212e-20, 3.6521153887674253e-20,
+ 3.5622237960646127e-20, 3.470731095738857e-20, 3.377510656357792e-20, 3.282419040754845e-20,
+ 3.1852926960062177e-20, 3.085943752802367e-20, 2.9841546217580957e-20, 2.879670935396108e-20,
+ 2.772192169113539e-20, 2.661358930495413e-20, 2.5467353391178318e-20, 2.4277839478989958e-20,
+ 2.303828920285994e-20, 2.1739999061414015e-20, 2.037142499071807e-20, 1.8916669455626665e-20,
+ 1.7352728004959384e-20, 1.56439466915464e-20, 1.3729109753658277e-20, 1.1483304366567183e-20,
+ 8.53241131926212e-21, 0.0};
+ /** Overhang table. Y_i = f(X_i). */
+ private static final double[] Y = {2.532379772713818e-23, 5.310835823923221e-23, 8.26022457065042e-23,
+ 1.134603744347431e-22, 1.4547828564666417e-22, 1.7851865078182134e-22, 2.1248195450141036e-22,
+ 2.472922973401801e-22, 2.8288961626257085e-22, 3.1922503684288075e-22, 3.5625791217647975e-22,
+ 3.9395384018258527e-22, 4.322832822347196e-22, 4.712205689742199e-22, 5.107431651499161e-22,
+ 5.508311133935702e-22, 5.914666050219951e-22, 6.32633643158829e-22, 6.743177743380035e-22,
+ 7.165058718271907e-22, 7.591859586388e-22, 8.023470614308747e-22, 8.459790887588371e-22,
+ 8.900727287454353e-22, 9.346193623979475e-22, 9.7961098965457e-22, 1.0250401658767016e-21,
+ 1.070899946982291e-21, 1.117183841780181e-21, 1.1638857703464862e-21, 1.211000027502763e-21,
+ 1.2585212506275e-21, 1.3064443911684845e-21, 1.3547646893321801e-21, 1.4034776515135506e-21,
+ 1.4525790301004666e-21, 1.5020648053444311e-21, 1.5519311690365945e-21, 1.60217450976698e-21,
+ 1.6527913995771288e-21, 1.7037785818432865e-21, 1.7551329602497868e-21, 1.8068515887312395e-21,
+ 1.858931662278158e-21, 1.9113705085142316e-21, 1.964165579965045e-21, 2.0173144469479217e-21,
+ 2.0708147910210758e-21, 2.1246643989375575e-21, 2.178861157055798e-21, 2.233403046164028e-21,
+ 2.28828813668061e-21, 2.343514584196453e-21, 2.39908062532932e-21, 2.4549845738630073e-21,
+ 2.5112248171471613e-21, 2.5677998127359586e-21, 2.6247080852460518e-21, 2.681948223416096e-21,
+ 2.73951887735187e-21, 2.7974187559425357e-21, 2.8556466244349068e-21, 2.914201302153814e-21,
+ 2.973081660357729e-21, 3.0322866202197593e-21, 3.0918151509250072e-21, 3.151666267876049e-21,
+ 3.2118390309989992e-21, 3.2723325431432467e-21, 3.3331459485685267e-21, 3.3942784315135004e-21,
+ 3.455729214840488e-21, 3.51749755875142e-21, 3.579582759570448e-21, 3.641984148589033e-21,
+ 3.7047010909696115e-21, 3.7677329847042535e-21, 3.831079259624996e-21, 3.8947393764627574e-21,
+ 3.958712825951976e-21, 4.0229991279783226e-21, 4.087597830767002e-21, 4.152508510109364e-21,
+ 4.2177307686256654e-21, 4.283264235061998e-21, 4.34910856361952e-21, 4.4152634333142514e-21,
+ 4.481728547365803e-21, 4.5485036326135354e-21, 4.6155884389587065e-21, 4.682982738831299e-21,
+ 4.750686326680256e-21, 4.818699018485977e-21, 4.887020651293957e-21, 4.955651082768556e-21,
+ 5.0245901907659065e-21, 5.093837872925075e-21, 5.163394046276591e-21, 5.2332586468675656e-21,
+ 5.303431629402611e-21, 5.3739129668998646e-21, 5.444702650361428e-21, 5.515800688457595e-21,
+ 5.5872071072242535e-21, 5.658921949772901e-21, 5.730945276012736e-21, 5.803277162384305e-21,
+ 5.875917701604242e-21, 5.948867002420633e-21, 6.022125189378572e-21, 6.0956924025955166e-21,
+ 6.169568797546033e-21, 6.243754544855583e-21, 6.3182498301029956e-21, 6.393054853631293e-21,
+ 6.468169830366561e-21, 6.5435949896445654e-21, 6.61933057504483e-21, 6.695376844231907e-21,
+ 6.7717340688035926e-21, 6.848402534145828e-21, 6.925382539294077e-21, 7.002674396800946e-21,
+ 7.080278432609835e-21, 7.158194985934437e-21, 7.236424409143883e-21, 7.314967067653352e-21,
+ 7.393823339819985e-21, 7.472993616843931e-21, 7.552478302674367e-21, 7.632277813920362e-21,
+ 7.71239257976641e-21, 7.792823041892541e-21, 7.873569654398836e-21, 7.954632883734263e-21,
+ 8.036013208629687e-21, 8.117711120034972e-21, 8.199727121060036e-21, 8.282061726919792e-21,
+ 8.364715464882844e-21, 8.447688874223886e-21, 8.530982506179678e-21, 8.614596923908543e-21,
+ 8.698532702453287e-21, 8.782790428707488e-21, 8.867370701385059e-21, 8.952274130993032e-21,
+ 9.037501339807492e-21, 9.123052961852595e-21, 9.208929642882634e-21, 9.295132040367049e-21,
+ 9.381660823478398e-21, 9.468516673083161e-21, 9.555700281735394e-21, 9.643212353673148e-21,
+ 9.731053604817628e-21, 9.819224762775044e-21, 9.907726566841127e-21, 9.996559768008253e-21,
+ 1.0085725128975164e-20, 1.0175223424159242e-20, 1.0265055439711297e-20, 1.0355221973532876e-20,
+ 1.0445723835296011e-20, 1.0536561846465444e-20, 1.0627736840323247e-20, 1.0719249661995874e-20,
+ 1.0811101168483563e-20, 1.0903292228692131e-20, 1.0995823723467109e-20, 1.1088696545630196e-20,
+ 1.118191160001806e-20, 1.1275469803523424e-20, 1.1369372085138467e-20, 1.14636193860005e-20,
+ 1.155821265943994e-20, 1.1653152871030541e-20, 1.1748440998641906e-20, 1.1844078032494261e-20,
+ 1.1940064975215492e-20, 1.2036402841900448e-20, 1.2133092660172487e-20, 1.2230135470247318e-20,
+ 1.2327532324999065e-20, 1.2425284290028643e-20, 1.2523392443734356e-20, 1.2621857877384821e-20,
+ 1.2720681695194142e-20, 1.2819865014399386e-20, 1.2919408965340364e-20, 1.3019314691541709e-20,
+ 1.311958334979729e-20, 1.3220216110256947e-20, 1.332121415651558e-20, 1.342257868570459e-20,
+ 1.35243109085857e-20, 1.3626412049647167e-20, 1.3728883347202408e-20, 1.3831726053491038e-20,
+ 1.393494143478237e-20, 1.403853077148138e-20, 1.4142495358237157e-20, 1.424683650405386e-20,
+ 1.4351555532404212e-20, 1.445665378134558e-20, 1.45621326036386e-20, 1.466799336686844e-20,
+ 1.4774237453568695e-20, 1.4880866261347982e-20, 1.498788120301918e-20, 1.5095283706731464e-20,
+ 1.520307521610505e-20, 1.53112571903688e-20, 1.5419831104500607e-20, 1.5528798449370678e-20,
+ 1.5638160731887733e-20, 1.5747919475148132e-20, 1.5858076218588015e-20, 1.596863251813844e-20,
+ 1.607958994638363e-20, 1.619095009272232e-20, 1.6302714563532247e-20, 1.6414884982337896e-20,
+ 1.6527462989981453e-20, 1.6640450244797108e-20, 1.675384842278868e-20, 1.6867659217810695e-20,
+ 1.6981884341752875e-20, 1.7096525524728213e-20, 1.721158451526456e-20, 1.7327063080499912e-20,
+ 1.7442963006381335e-20, 1.7559286097867713e-20, 1.767603417913626e-20, 1.779320909379297e-20,
+ 1.7910812705086994e-20, 1.8028846896129066e-20, 1.8147313570114e-20, 1.82662146505474e-20,
+ 1.8385552081476575e-20, 1.8505327827725806e-20, 1.8625543875136006e-20, 1.874620223080887e-20,
+ 1.8867304923355594e-20, 1.8988854003150238e-20, 1.911085154258786e-20, 1.9233299636347447e-20,
+ 1.9356200401659812e-20, 1.9479555978580487e-20, 1.9603368530267746e-20, 1.9727640243265847e-20,
+ 1.9852373327793618e-20, 1.9977570018038445e-20, 2.010323257245582e-20, 2.0229363274074546e-20,
+ 2.03559644308077e-20, 2.0483038375769486e-20, 2.061058746759809e-20, 2.073861409078469e-20,
+ 2.0867120656008704e-20, 2.099610960047943e-20, 2.1125583388284243e-20, 2.1255544510743418e-20,
+ 2.1385995486771794e-20, 2.151693886324738e-20, 2.1648377215387072e-20, 2.1780313147129627e-20,
+ 2.1912749291526057e-20, 2.204568831113762e-20, 2.2179132898441537e-20, 2.2313085776244664e-20,
+ 2.2447549698105236e-20, 2.2582527448762922e-20, 2.2718021844577323e-20, 2.285403573397516e-20,
+ 2.2990571997906318e-20, 2.3127633550308938e-20, 2.3265223338583805e-20, 2.3403344344078233e-20,
+ 2.3541999582579633e-20, 2.3681192104819063e-20, 2.3820924996984908e-20, 2.396120138124703e-20,
+ 2.4102024416291538e-20, 2.4243397297866505e-20, 2.438532325933887e-20, 2.452780557226279e-20,
+ 2.467084754695973e-20, 2.4814452533110573e-20, 2.4958623920360058e-20, 2.5103365138933835e-20,
+ 2.5248679660268454e-20, 2.539457099765463e-20, 2.5541042706894083e-20, 2.5688098386970325e-20,
+ 2.583574168073375e-20, 2.5983976275601352e-20, 2.61328059042715e-20, 2.6282234345454126e-20,
+ 2.643226542461671e-20, 2.6582903014746527e-20, 2.6734151037129546e-20, 2.6886013462146377e-20,
+ 2.7038494310085842e-20, 2.7191597651976473e-20, 2.7345327610436566e-20, 2.7499688360543205e-20,
+ 2.7654684130720776e-20, 2.781031920364953e-20, 2.7966597917194705e-20, 2.8123524665356816e-20,
+ 2.8281103899243675e-20, 2.8439340128064684e-20, 2.859823792014815e-20, 2.875780190398213e-20,
+ 2.891803676927963e-20, 2.907894726806858e-20, 2.9240538215807684e-20, 2.9402814492528446e-20,
+ 2.9565781044004507e-20, 2.972944288294883e-20, 2.9893805090239645e-20, 3.005887281617601e-20,
+ 3.02246512817638e-20, 3.039114578003308e-20, 3.055836167738775e-20, 3.072630441498844e-20,
+ 3.0894979510169736e-20, 3.106439255789257e-20, 3.123454923223312e-20, 3.1405455287909063e-20,
+ 3.157711656184457e-20, 3.174953897477506e-20, 3.1922728532893043e-20, 3.209669132953634e-20,
+ 3.2271433546919926e-20, 3.2446961457912936e-20, 3.26232814278621e-20, 3.280039991646321e-20,
+ 3.2978323479682113e-20, 3.3157058771726903e-20, 3.3336612547072853e-20, 3.3516991662541965e-20,
+ 3.369820307943883e-20, 3.388025386574477e-20, 3.406315119837208e-20, 3.424690236548051e-20,
+ 3.4431514768858065e-20, 3.4616995926368224e-20, 3.4803353474466e-20, 3.4990595170785116e-20,
+ 3.517872889679876e-20, 3.5367762660556557e-20, 3.555770459950039e-20, 3.5748562983361843e-20,
+ 3.594034621714422e-20, 3.6133062844192156e-20, 3.6326721549351945e-20, 3.652133116222594e-20,
+ 3.671690066052438e-20, 3.691343917351836e-20, 3.711095598559755e-20, 3.7309460539936645e-20,
+ 3.750896244227467e-20, 3.770947146481129e-20, 3.79109975502247e-20, 3.811355081581572e-20,
+ 3.831714155778291e-20, 3.852178025563392e-20, 3.872747757673826e-20, 3.893424438102728e-20,
+ 3.914209172584698e-20, 3.935103087096993e-20, 3.956107328377266e-20, 3.977223064458528e-20,
+ 3.998451485222028e-20, 4.019793802968809e-20, 4.041251253010693e-20, 4.0628250942815264e-20,
+ 4.08451660996954e-20, 4.106327108171703e-20, 4.1282579225710425e-20, 4.1503104131378944e-20,
+ 4.172485966856146e-20, 4.194785998475555e-20, 4.2172119512913083e-20, 4.2397652979520307e-20,
+ 4.26244754129752e-20, 4.285260215227567e-20, 4.3082048856032696e-20, 4.3312831511823486e-20,
+ 4.35449664459004e-20, 4.377847033327237e-20, 4.4013360208176433e-20, 4.424965347495792e-20,
+ 4.44873679193791e-20, 4.472652172037699e-20, 4.4967133462292346e-20, 4.5209222147593173e-20,
+ 4.545280721011741e-20, 4.5697908528860855e-20, 4.5944546442338236e-20, 4.619274176354652e-20,
+ 4.6442515795561947e-20, 4.6693890347803697e-20, 4.694688775299949e-20, 4.720153088489046e-20,
+ 4.745784317671508e-20, 4.771584864051452e-20, 4.797557188730451e-20, 4.8237038148161644e-20,
+ 4.850027329627554e-20, 4.876530387002128e-20, 4.903215709711068e-20, 4.930086091988455e-20,
+ 4.957144402181263e-20, 4.9843935855272545e-20, 5.011836667068401e-20, 5.039476754708001e-20,
+ 5.0673170424202713e-20, 5.0953608136218094e-20, 5.123611444715016e-20, 5.152072408814347e-20,
+ 5.1807472796670477e-20, 5.2096397357809406e-20, 5.2387535647727967e-20, 5.268092667951877e-20,
+ 5.2976610651543945e-20, 5.3274628998459006e-20, 5.357502444509989e-20, 5.387784106343208e-20,
+ 5.4183124332777464e-20, 5.449092120355254e-20, 5.480128016477185e-20, 5.511425131559201e-20,
+ 5.542988644119667e-20, 5.574823909334829e-20, 5.606936467596343e-20, 5.639332053609944e-20,
+ 5.672016606077763e-20, 5.704996278010726e-20, 5.738277447721936e-20, 5.771866730556852e-20,
+ 5.805770991421623e-20, 5.839997358176981e-20, 5.874553235972036e-20, 5.909446322599911e-20,
+ 5.944684624965775e-20, 5.98027647676747e-20, 6.016230557499789e-20, 6.052555912905671e-20,
+ 6.089261977011434e-20, 6.126358595898756e-20, 6.163856053383874e-20, 6.201765098794606e-20,
+ 6.240096977058771e-20, 6.278863461343729e-20, 6.318076888516832e-20, 6.357750197730895e-20,
+ 6.397896972478401e-20, 6.438531486503798e-20, 6.479668754015973e-20, 6.521324584704252e-20,
+ 6.563515644132436e-20, 6.60625952016853e-20, 6.649574796205078e-20, 6.693481132039372e-20,
+ 6.737999353417576e-20, 6.78315155140629e-20, 6.82896119294466e-20, 6.87545324415615e-20,
+ 6.922654308270048e-20, 6.970592780328698e-20, 7.01929902125074e-20, 7.068805554299649e-20,
+ 7.119147287592182e-20, 7.170361767000327e-20, 7.222489464688847e-20, 7.275574109635319e-20,
+ 7.329663067862371e-20, 7.384807781854906e-20, 7.44106428084867e-20, 7.498493776510197e-20,
+ 7.557163362186687e-20, 7.617146838671345e-20, 7.678525695702381e-20, 7.741390286755859e-20,
+ 7.805841245914747e-20, 7.871991210882315e-20, 7.939966937313497e-20, 8.009911919213852e-20,
+ 8.081989672282774e-20, 8.156387898169583e-20, 8.233323837990194e-20, 8.313051260166436e-20,
+ 8.395869739690673e-20, 8.482137224231827e-20, 8.572287440027122e-20, 8.666854644243818e-20,
+ 8.766509934779227e-20, 8.872116535656441e-20, 8.984817900681022e-20, 9.106186379912279e-20,
+ 9.238493381053173e-20, 9.385252216864754e-20, 9.552479913718005e-20, 9.752412557725429e-20,
+ 1.0021490936397442e-19, 1.0842021724855044e-19};
+
+ /** Underlying source of randomness. */
+ protected final UniformRandomProvider rng;
+
+ /**
+ * @param rng Generator of uniformly distributed random numbers.
+ */
+ ModifiedZigguratExponentialSampler512(UniformRandomProvider rng) {
+ this.rng = rng;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public double sample() {
+ return createSample();
+ }
+
+ /**
+ * Creates the exponential sample with {@code mean = 1}.
+ *
+ * <p>Note: This has been extracted to a separate method so that the recursive call
+ * when sampling tries again targets this function. This allows sub-classes
+ * to override the sample method to generate a sample with a different mean using:
+ * <pre>
+ * @Override
+ * public double sample() {
+ * return super.sample() * mean;
+ * }
+ * </pre>
+ * Otherwise the sub-class {@code sample()} method will recursively call
+ * the overloaded sample() method when trying again which creates a bad sample due
+ * to compound multiplication of the mean.
+ *
+ * @return the sample
+ */
+ final double createSample() {
+ final long x = nextLong();
+ // Float multiplication squashes these last 9 bits, so they can be used to sample i
+ final int i = ((int) x) & 0x1ff;
+
+ if (i < I_MAX) {
+ // Early exit.
+ // This branch is called about 0.992192 times per call into createSample.
+ // Note: Frequencies have been empirically measured for the first call to
+ // createSample; recursion due to retries have been ignored. Frequencies sum to 1.
+ return X[i] * (x & MAX_INT64);
+ }
+ // For the first call into createSample:
+ // Recursion frequency = 0.000232210
+ // Overhang frequency = 0.00764647
+ final int j = expSampleA();
+ return j == 0 ? X_0 + createSample() : expOverhang(j);
+ }
+
+ /**
+ * Alias sampling.
+ * See http://scorevoting.net/WarrenSmithPages/homepage/sampling.abs
+ *
+ * @return the alias
+ */
+ protected int expSampleA() {
+ final long x = nextLong();
+ // j <- I(0, 512)
+ final int j = ((int) x) & 0x1ff;
+ return x >= IPMF[j] ? MAP[j] : j;
+ }
+
+ /**
+ * Draws a PRN from overhang.
+ *
+ * @param j Index j (must be {@code > 0})
+ * @return the sample
+ */
+ protected double expOverhang(int j) {
+ // To sample a unit right-triangle:
+ // U_x <- min(U_1, U_2)
+ // distance <- | U_1 - U_2 |
+ // U_y <- 1 - (U_x + distance)
+ long ux = randomInt63();
+ long uDistance = randomInt63() - ux;
+ if (uDistance < 0) {
+ uDistance = -uDistance;
+ ux -= uDistance;
+ }
+ // _FAST_PRNG_SAMPLE_X(xj, ux)
+ final double x = fastPrngSampleX(j, ux);
+ if (uDistance >= IE_MAX) {
+ // Early Exit: x < y - epsilon
+ return x;
+ }
+ // _FAST_PRNG_SAMPLE_Y(j, pow(2, 63) - (ux + uDistance))
+ // Long.MIN_VALUE is used as an unsigned int with value 2^63:
+ // uy = Long.MIN_VALUE - (ux + uDistance)
+ return fastPrngSampleY(j, Long.MIN_VALUE - (ux + uDistance)) <= Math.exp(-x) ? x : expOverhang(j);
+ }
+
+ /**
+ * Generates a {@code long}.
+ *
+ * @return the long
+ */
+ protected long nextLong() {
+ return rng.nextLong();
+ }
+
+ /**
+ * Return a positive long in {@code [0, 2^63)}.
+ *
+ * @return the long
+ */
+ protected long randomInt63() {
+ return rng.nextLong() & MAX_INT64;
+ }
+
+ /**
+ * Auxilary function to see if rejection sampling is required in the overhang.
+ * See Fig. 2 in the main text.
+ *
+ * @param j j
+ * @param ux ux
+ * @return the sample
+ */
+ protected static double fastPrngSampleX(int j, long ux) {
+ return X[j] * TWO_POW_63 + (X[j - 1] - X[j]) * ux;
+ }
+
+ /**
+ * Auxilary function to see if rejection sampling is required in the overhang.
+ * See Fig. 2 in the main text.
+ *
+ * @param i i
+ * @param uy uy
+ * @return the sample
+ */
+ static double fastPrngSampleY(int i, long uy) {
+ return Y[i - 1] * TWO_POW_63 + (Y[i] - Y[i - 1]) * uy;
+ }
+ }
+
+ /**
* Throw an illegal state exception for the unknown parameter.
*
* @param parameter Parameter name