On Tue, 4 Feb 2025 17:20:45 -0500
Steven Rostedt [off-list ref] wrote:
x = rec->counter
x * (x - 1) * 1000 = (2^32 - 1) // use minus 1 just to be sure
x * (x - 1) = (2^32 - 1) / 1000
x^2 - x = (2^32 - 1) / 1000
x^2 - x - (2^32 - 1) / 1000 = 0
x = (-b +/- sqrt(b^2 - 4ac)) / 2a
a = 1
b = -1
c = -(2^32 - 1) / 1000 = -4294967.295
x = (-1 +/- sqrt((-1)^2 - 4 * -4294967.295)) / 2
And I did make a mistake, as b = -1, and the above should start with -(-1)
or 1 :-p
x = 2071.930 for 32bit
This should be: 2072.930
For 64bit we have
c = -(2^64 - 1) / 1000 = -18446744073709551.615
That makes
x = 135818790.812
And this needs to be: 135818791.812
quoted hunk ↗ jump to hunk
+/*
+ * The calculation for stddev will overflow when the counter
+ * algorithm overflows the long size:
+ *
+ * rec->counter * (rec->counter - 1) * 1000 >= 2^BITS_PER_LONG
+ *
+ * Using the quadratic equation: x = (-b +/- sqrt(b^2 - 4ac)) / 2a
+ * we can figure out what the max rec->counter is before it
+ * overflows.
+ *
+ * x = rec->counter
+ * x * (x - 1) * 1000 = 2^BITS_PER_LONG - 1 // -1 for rounding
+ * x * (x - 1) = (2^BITS_PER_LONG - 1) / 1000
+ * x^2 - x = (2^BITS_PER_LONG - 1) / 1000
+ * x^2 - x - (2^BITS_PER_LONG - 1) / 1000 = 0
+ *
+ * a = 1
+ * b = -1
+ * c = -(2^BITS_PER_LONG - 1) / 1000
+ *
+ * x = (1 +/- sqrt(1 - 4 * -(2^BITS_PER_LONG - 1) / 1000)) / 2
+ *
+ * For 32bit that is: x = 2072.930 (or 2072)
+ * For 64bit that is: x = 135818791.812 (or 135818791)
+ */
But in the patch, I redid the numbers and did not copy from the above, and
here I did it correctly.
-- Steve