3f:["$","title",null,{"children":"H2Histogram: A High Dynamic Range, Base-2 Histogram | IOP Systems | Observable"}] 45:T59c,texmdd`Bucket lookup is the primary operation for recording a value. The following algorithm only applies to positive integers (i.e. zero values are not allowed). Support for zero value is trivially added as a first step of lookup implementation. We represent the input value as a $n$-digit binary: $$V = (a_{n-1}a_{n-2}...a_0)_2$$ Looking up the right bucket offset $b$ for $V$ works as follows: 1. find the highest non-zero digit $h$. $h$ ($0 \le h \le n-1$) is such that $a_{h} = 1$ but $a_{i} = 0$ for all $i$ that satisfies $h < i otherwise, first compute $w = h - p$, and we can compute $b$ as $(w + 1) \times 2^{p} + (V - 2^{h}) \gg w$ #### Explanation In the above algorithm, the highest non-zero digit $h$ tells us the width of the bucket that should record the input value $V$. For $h \le p$ the bucket width is $2^0$; for $h = p + 1$ the bucket width is $2^1$; etc. For any positive $w$, the total number of buckets with a width *less than* $2^w$ is $(w+1) \times 2^p$. There are $2^p$ buckets of width $2^w$, with a lower bound $2^{h}$ as the value. To find out which bucket in this group is the right one for $V$, we compute the distance between $V$ and the lower bound, and divide that by the bucket width of the current group. Since all bounds are powers of 2, the division is converted to a bit shift. `46:T94a,texmd`In a naïve implementation, reporting a particular quantile $q$ requires traversing all the buckets once. Even if the total number of values in the histogram is known, the number of buckets to traverse is still linear to the total number of buckets. There are a couple things to consider during implementation regarding bias in reporting. Because each bucket covers a range except for the precise ones, a decision needs to be made about what value in that range to report when we do a quantile lookup. We also need to consider how to interpret results that don't fall neatly in a single bucket— for example, when there are 3 values in the histogram and the quantile in question is $0.5$. For the latter, we can use the [nearest-rank method](https://en.wikipedia.org/wiki/Percentile#The_nearest-rank_method) to find the nearest bucket with records. Alternatively, it is also possible to extrapolate an in-between value based on existing data. Each method has its drawbacks. For example, linear interpretation could lead to a confusing situation where the interpreted value is deemed impossible given how values are measured. #### Optimization To reduce the number of buckets traversed during lookup, one can store the total number of counts, $C$, across all buckets, and return when the buckets traversed so far yields a cumulative count greater than $q \times C$ (if traversing from lowest bucket) or $(1 - q) \times C$ (if traversing from highest bucket). Further reduction can be achieved by using some type of "sketch" that stores cumulative values across multiple buckets, which allows the cursor to jump over many buckets at a time. The tradeoff is multiple values will need to be updated for each recording, and more space will be used. There are two typical scenarios where H2Histogram is deployed. The first one is to check if there is any SLO violation, such as p99 latency. In this case, the percentile of interest is very close to highest end, so a simple global count and backward traversal can greatly reduce the number of buckets visited. The other one is to create a snapshot of value distribution by reporting several pre-defined percentiles at once, such as p25, p50, p75, p90, p95, p99... In this case, it is probably the most efficient to create APIs that allow multiple quantiles to be reported in a single sweeping trip through all the buckets. `47:T523,texmd`Often, the range of plausible values has both an upper and lower bound. In the current H2Histogram design, expressing an upper bound is straightforward— just providing the smallest $n$ that fits the value. But we haven't discussed lower bound. In fact, having a lower bound could potentially meaningfully reduce the amount of memory needed to store a histogram, because smaller values are stored in finer buckets. For example, For $n = 32$ and $p = 8$, if we know the lower bound of values is 1024, we can eliminate 768 out of 6400 buckets, a 12% reduction. More precisely, if we know the lower bound is at least $2^l$, we can eliminate $2^l$ buckets (if $l \le p+1$) or $(l - p + 1) \times 2^p$ buckets (if $l > p + 1$). How common do values have lower bounds? In high-level time measurements in particular, this condition is extremely common. For example, if we use a clock with nanosecond precision to track common software operations, the lower bounds are significantly higher than the resolution of the measurement. Many syscalls are measured by microseconds, request/response time is often measured by milliseconds. This means we can expect $l$ to be in the range of 10 to 20 in a lot of real life use cases. Use the following calculator to see how much space a truncated histogram can save you: `48:T4ff,summarize = (n_val = 64) => { const KiB = 1024; const MiB = 1048576; let arr = []; var nbucket; var error; var size_base; var size_uint8; var size_uint16; var size_uint32; var size_uint64; for (const k of p_vals.values()) { nbucket = BigInt(2 ** k * (n_val - k + 1)); error = (2 ** -k * 100).toPrecision(3) + "%"; size_base = Number(nbucket); size_uint8 = size_base > MiB ? (size_base / MiB).toFixed(1) + " MiB" : (size_base / KiB).toFixed(1) + " KiB"; size_base = size_base * 2; size_uint16 = size_base > MiB ? (size_base / MiB).toFixed(1) + " MiB" : (size_base / KiB).toFixed(1) + " KiB"; size_base = size_base * 2; size_uint32 = size_base > MiB ? (size_base / MiB).toFixed(1) + " MiB" : (size_base / KiB).toFixed(1) + " KiB"; size_base = size_base * 2; size_uint64 = size_base > MiB ? (size_base / MiB).toFixed(1) + " MiB" : (size_base / KiB).toFixed(1) + " KiB"; arr.push({ p: k, "relative error": error, "#bucket": String(nbucket), "size (8-bit)": size_uint8, "size (16-bit)": size_uint16, "size (32-bit)": size_uint32, "size (64-bit)": size_uint64 }); } return arr; }49:T5f6,function texmd() { // First perform tex replacement on all the strings in the template // Each piece of tex is replaced with a placeholder for now, to keep it away from the markdown parser var display_maths = []; var inline_maths = []; // Note use of raw strings here; important to keep backslashes intact so tex can see them let strings = arguments[0].raw.map(function (string) { // Then extract all the TeX code and replace it with placeholders (so it won't be run through md) string = string.replace(/\$\$([^\$]*)\$\$/g, (s, m) => { var i = display_maths.push(m) - 1; return `\n\n

\n\n`; }); string = string.replace(/\$([^\$]*)\$/g, (s, m) => { var i = inline_maths.push(m) - 1; return ``; }); return string; }); // Now we can run this through markdown with proper ${} substitutions var node = md(strings, ...Array.prototype.slice.call(arguments, 1)); // And finally replace TeX placeholders with output of tex() node.querySelectorAll("span.imath").forEach((span) => { var i = parseInt(span.attributes.n.value); if (inline_maths[i] === undefined) throw "What?"; span.appendChild(tex`${inline_maths[i]}`); span.style["font-size"] = ".95em"; }); node.querySelectorAll("div.dmath").forEach((div) => { var i = parseInt(div.attributes.n.value); div.appendChild(tex.block`${display_maths[i]}`); div.style["font-size"] = ".95em"; }); return node; }4a:[] 43:{"id":"28a19540b5b49e00","slug":"h2-histogram","title":"H2Histogram: A High Dynamic Range, Base-2 Histogram","thumbnail":"0b42636b4c3547b7e54255e1157b7435c3238701e57863f2018baee393ab57c7","access_level":"unlisted","create_time":"$D2023-09-19T19:05:51.089Z","update_time":"$D2024-03-13T06:24:46.671Z","view_time":null,"first_public_time":"$D2023-09-21T00:04:50.546Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"adccd89f4f842c39","login":"iopsystems","name":"IOP Systems","avatar_url":"https://avatars-next.observableusercontent.com/05e878af549d661b26814b88369eebefba7bf6d71e5938405bc2b055e716c7f1","tier":"pro_2024","bio":""},"version":882,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"9ee81eea08a18a48","login":"yaoyue","name":"Yao Yue","avatar_url":"https://avatars-next.observableusercontent.com/ee26da502ad2edbd126cd2d377bbb79a26076012d69a31b6746f43886d653fbd","tier":null,"bio":"Yao Yue’s account associated with IOP Systems Inc."}],"members":[{"type":"team","id":"adccd89f4f842c39","login":"iopsystems","name":"IOP Systems","avatar_url":"https://avatars-next.observableusercontent.com/05e878af549d661b26814b88369eebefba7bf6d71e5938405bc2b055e716c7f1","tier":"pro_2024","role":"editor"},{"type":"individual","id":"9ee81eea08a18a48","login":"yaoyue","name":"Yao Yue","avatar_url":"https://avatars-next.observableusercontent.com/ee26da502ad2edbd126cd2d377bbb79a26076012d69a31b6746f43886d653fbd","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"titling":"auto","title":"H2Histogram: A High Dynamic Range, Base-2 Histogram","cells":[{"id":0,"value":"# H2Histogram: A High Dynamic Range, Base-2 Histogram ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":518,"value":"The H2Histogram provides a histogram that is conceptually similar to [HdrHistogram](http://www.hdrhistogram.org/), with modifications to the bucket construction algorithm and configurable options.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":547,"value":"// toc()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":46,"value":"## Background and Assumptions","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":513,"value":"### Background\n\nRecording and reporting quantile metrics is a very common task, and highly valuable in characterizing workload and performance. Usually, system input/output and behavior have a wide but bounded range of acceptable values, and tracking the distribution within this range at a certain precision provides rich insights into the workload. In high-throughput scenarios, HdrHistogram is highly popular due to its low recording overhead. However, HdrHistogram is a base-10 design. We believe a base-2 variant works even better in terms of speed, simplicity, and configurability.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":521,"value":"### Assumptions\n\nBelow are our core assumptions:\n1. Bucket widths are powers of 2, and monotonically increasing for larger values\n2. We want to accept any natural number up to the maximum value allowed\n4. Using relative error as a constraint, the goal is to primarily maximize recording throughput and secondarily minimize memory space","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":524,"value":"\n### Goals\n\nH2Histogram aims to provide a simpler implementation, finer-grain configuration, and more efficient runtime compared to the reference implementation provided by HdrHistogram.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":50,"value":"## Basic Parameters","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":21,"value":"texmd`**maximum value in histogram**: $$N = 2^n - 1$$ This is the largest value the histogram can track, parameterized by the exponent, $n$.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":848,"value":"range_input(viewof n, tex`n`, 8, 64, 1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"texmdd`for $n=${n}$, $N$ = ${N.toString()}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":34,"value":"texmdd`**relative error**: $$e = 2^{-p}$$ This is the upper bound on the relative error created by value quantization, parameterized by the exponent (of its inverse), $p$.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":856,"value":"range_input(viewof p, tex`p`, 2, 22, 1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"texmdd`for $p=${p}$, $e = ${e.toPrecision(3)}$`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":"**Note**: the concept of relative error does not apply when the exact integer value is recorded.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":41,"value":"## Bucket Construction","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":43,"value":"texmdd`We use a bucket width of just 1 for small integers. As the absolute value goes up, we can double the bucket width without violating relative error constraint, *e*.\n\n\nThe smallest value that allows bucket width to go from ${2 ** 0} ($2^0$) to ${\n 2 ** 1\n} ($2^1$) is $\\frac{2}{e}$ (or $2^{p+1}$). For $p = ${p}$, that value is ${\n 2 ** p * 2\n}.\n\nThis means there are $2^{p+1}$ precise buckets.\n\nBucket width can be doubled from ${2 ** 1} ($2^1$) to ${\n 2 ** 2\n} ($2^2$) for values great than or equal to $\\frac{4}{e}$ (or $2^{p+2}$). For $p = ${p}$, that value is ${\n 2 ** p * 4\n}.\n\nThis also means there are $2^p$ buckets of width 2. \n\nSo on and so forth, until the threshold value reaches the maximum value $N$. At that point, there will be $(n - p)$ **groups** of buckets of doubling widths. For $n = ${n}$ and $p = ${p}$, the number of groups is ${\n n - p\n}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":284,"value":"**Note**: When ${tex`p = n - 1`}, the histogram will have the exact same number of buckets as there are values. Notions of absolute and relative errors do not apply in such a histogram.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":120,"value":"### Bucket Summary","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":123,"value":"texmdd`\n- Total number of buckets: $(n-p+1) \\times 2^p$. For $n = ${n}$ and $p = ${p}$, that is ${total_buckets.toString()} buckets\n- Histogram size: number of buckets multiplied by counter size. For $n = ${n}$ and $p = ${p}$, that is ${(\n (total_buckets.valueOf() * 8n) /\n 1024n\n).toString()} KiB (64-bit counters) or ${(\n (total_buckets.valueOf() * 4n) /\n 1024n\n).toString()} KiB (32-bit counters)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":664,"value":"texmd`The table below gives a sense of the total number of buckets and histogram size for various $p$ values, assuming we want to record values up to max unsigned 64-bit integer.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":792,"value":"html`${table_with_header(summary64)}

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":364,"value":"### Bucket Lookup","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":432,"value":"$45","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":441,"value":"texmdd`\n#### Optimization\nOn CPUs supporting SSE4, $h$ can be most efficiently computed by using $\\texttt{LZCNT}$ instruction.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":479,"value":"texmdd`\n\nBelow are a few lookup examples assuming $p = 9$:\n\n- $V=1$: $h = 0, B = 1$\n- $V=1023$: $h = 9, B = 1023$\n- $V=1024$: $h = 10, w = 1, B = 2 \\times 512 + (1024 - 2^{10}) \\gg 1 = 1024$\n- $V=2048$: $h = 11, d = 2, B = 3 \\times 512 + (2048 - 2^{11}) \\gg 2 = 1536$\n- $V=2052$: $h = 11, d = 2, B = 3 \\times 512 + (2052 - 2^{11}) \\gg 2 = 1537$\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":489,"value":"### Quantile Lookup","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":491,"value":"$46","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":366,"value":"## Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":368,"value":"### Counter Type","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":370,"value":"Recording counts as integers provides precise reading within counter range, which means it is important to using enough bits to cover the accumulative counts during recording period. This generally means 8-bit, 16-bit, 32-bit, or 64-bit unsigned integers.\n\nRecording counts as floating point numbers increases the dynamic range of individual buckets at the cost of precision. Since H2Histogram has the concept of precision as a configurable option, it is possible to consider the use of floating point types in conjunction with overall precision.\n\nBelow is a table of the range and precision limits for different data types when used to record counts:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":375,"value":"texmd`\n| Type | Range Limit | Relative Error |\n|-----------------------|----------------------|------------------|\n| 8-bit integer | $255$ | \\- (precise) |\n| 16-bit integer | $65535$ | \\- (precise) |\n| 32-bit integer | $2^{32} - 1$ | \\- (precise) |\n| 64-bit integer | $2^{64} - 1$ | \\- (precise) |\n| 16-bit (half) float | $65519$ | $2^{-10}$ |\n| 32-bit (single) float | $\\approx 2^{128}$ | $2^{-23}$ |\n| 64-bit (double) float | $\\approx 2^{1024}$ | $2^{-52}$ |\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":539,"value":"From the above table, it should be obvious that if considering using 16-bit numbers or less, integer types are strictly superior; for 32- and 64-bit numbers, the choice should be based on potential range of the highest single-bucket count.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":549,"value":"### Truncated Histogram","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":551,"value":"$47","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":832,"value":"range_input(viewof l, tex`l`, 0, n - 1, 1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":573,"value":"texmdd`**number of buckets (original histogram)**: ${total_buckets.toString()} `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":579,"value":"texmdd`**number of buckets (truncated histogram)**: ${(\n total_buckets - truncated_buckets\n).toString()} `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":603,"value":"texmdd`**buckets saved**: ${truncated_buckets.toString()} (${reduction_pct.toFixed(\n 1\n)}%) `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":428,"value":"privateCellDelimiter = html`\n\n

\n
\n
\n
`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":839,"value":"### Inputs","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":3,"value":"viewof n = Inputs.input(64)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"viewof p = Inputs.input(10)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":567,"value":"viewof l = Inputs.input(10)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":843,"value":"### Data","pinned":true,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":690,"value":"summary64 = summarize(64)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":752,"value":"summary32 = summarize(32)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":670,"value":"$48","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":746,"value":"p_vals = [...Array(15).keys()].splice(2)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":329,"value":"total_buckets = BigInt(2 ** p * (n - p + 1))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":598,"value":"truncated_buckets = BigInt(l > p + 1 ? (l - p + 1) * 2 ** p : 2 ** l)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":610,"value":"truncated_buckets","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":616,"value":"reduction_pct = (Number(truncated_buckets) / Number(total_buckets)) * 100","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":344,"value":"buckets = compute_bucket()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":85,"value":"function compute_bucket() {\n let buckets = Array();\n let lower = BigInt(0);\n let total_buckets = BigInt(0);\n for (var w = 0; w + p < n; w++) {\n var width = BigInt(2 ** w);\n var upper = BigInt(2 ** (p + w + 1));\n var group_size = BigInt((upper - lower) / width);\n total_buckets += group_size;\n buckets.push({\n width: width,\n lower: lower,\n upper: upper,\n buckets: group_size\n });\n lower = upper;\n }\n\n return buckets;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":244,"value":"N = BigInt(2 ** n) - 1n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"e = 1 / 2 ** p","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":142,"value":"$49","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":827,"value":"### Imports","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":829,"value":"import { range_input } from \"@iopsystems/utility-functions\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":164,"value":"import { texmdd } from \"@aziis98/dynamic-katex-within-markdown\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":544,"value":"import {toc} from \"@nebrius/indented-toc\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":790,"value":"import { table_with_header } from \"@iopsystems/utility-functions\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4a","stdlib":"1"}} 44:"$43:body" 3e:E{"digest":"NEXT_REDIRECT;replace;/@iopsystems/h2-histogram;307;"}