vendor/bc/6.7.5

4 files changed, 426 insertions, 0 deletions

diff --git a/scripts/sqrt_frac_guess.bc b/scripts/sqrt_frac_guess.bc
new file mode 100644
index 000000000000..5938cfcc7cba
--- /dev/null
+++ b/scripts/sqrt_frac_guess.bc
@@ -0,0 +1,126 @@
+#! /usr/bin/bc
+#
+# SPDX-License-Identifier: BSD-2-Clause
+#
+# Copyright (c) 2018-2023 Gavin D. Howard and contributors.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are met:
+#
+# * Redistributions of source code must retain the above copyright notice, this
+#   list of conditions and the following disclaimer.
+#
+# * Redistributions in binary form must reproduce the above copyright notice,
+#   this list of conditions and the following disclaimer in the documentation
+#   and/or other materials provided with the distribution.
+#
+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+# POSSIBILITY OF SUCH DAMAGE.
+#
+
+scale = 20
+
+# Adjust this number to try ranges below different powers of 10.
+shift = 4
+
+# Adjust this to try extra digits. For example, a value of one means that one
+# digit is checked (such as 0.09 through 0.01), a value of two means that two
+# digits are checked (0.090 through 0.010), etc.
+max = shift + 2
+
+n = (9 >> shift)
+inc = (1 >> max)
+stop = (1 >> shift)
+
+# Uncomment this to test the high part of the ranges.
+#n += (1 - (1 >> max + 5)) >> shift
+
+for (i = n; i >= stop; i -= inc)
+{
+	# This is the lower limit.
+	t1 = sqrt(1/(3*i))
+
+	# Start with the inverse.
+	t2 = (1/i)
+
+	# And take half its length of course.
+	l = length(t2$)/2
+
+	temp = i
+	odd = 0
+
+	# We go by powers of 10 below, but there is a degenerate case: an exact
+	# power of 10, for which length() will return one digit more. So we check
+	# for that and fix it.
+	while (temp < 1)
+	{
+		temp <<= 1
+		odd = !odd
+	}
+
+	if (temp == 1)
+	{
+		odd = !odd
+	}
+
+	print "i:  ", i, "\n"
+	print "t2: ", t2, "\n"
+	#print "l:  ", l, "\n"
+	print "odd: ", odd, "\n"
+
+	if (odd)
+	{
+		# Limit between 6 and 7.5.
+		limit1 = 6.7 >> (l$ * 2 + 1)
+
+		# Limit between 1.5 and 1.83-ish.
+		limit2 = 1.7 >> (l$ * 2 + 1)
+		print "limit1: ", limit1, "\n"
+		print "limit2: ", limit2, "\n"
+
+		if (i >= limit1)
+		{
+			t2 = (t2 >> l$)
+		}
+		else if (i >= limit2)
+		{
+			t2 = (t2 >> l$) / 2
+		}
+		else
+		{
+			t2 = (t2 >> l$) / 4
+		}
+	}
+	else
+	{
+		# Limit between 2.4 and 3.
+		limit = 2.7 >> (l$ * 2)
+		print "limit: ", limit, "\n"
+
+		if (i >= limit)
+		{
+			t2 = (t2 >> l$) * 2
+		}
+		else
+		{
+			t2 = (t2 >> l$)
+		}
+	}
+	#t2 = 1
+	t3 = sqrt(5/(3*i))
+	good = (t1 < t2 && t2 < t3)
+
+	print t1, " < ", t2, " < ", t3, ": ", good, "\n\n"
+	if (!good) sqrt(-1)
+}
+
+halt
diff --git a/scripts/sqrt_int_guess.bc b/scripts/sqrt_int_guess.bc
new file mode 100644
index 000000000000..551a06eb2e6d
--- /dev/null
+++ b/scripts/sqrt_int_guess.bc
@@ -0,0 +1,94 @@
+#! /usr/bin/bc -l
+#
+# SPDX-License-Identifier: BSD-2-Clause
+#
+# Copyright (c) 2018-2023 Gavin D. Howard and contributors.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are met:
+#
+# * Redistributions of source code must retain the above copyright notice, this
+#   list of conditions and the following disclaimer.
+#
+# * Redistributions in binary form must reproduce the above copyright notice,
+#   this list of conditions and the following disclaimer in the documentation
+#   and/or other materials provided with the distribution.
+#
+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+# POSSIBILITY OF SUCH DAMAGE.
+#
+
+# Adjust this number to try ranges above different powers of 10.
+max = 0
+
+n = (1 << max)
+
+# Uncomment this to test the high part of the ranges.
+#n += (1 - (1 >> 10))
+
+n
+
+# Loop from the start number to the next power of 10.
+for (i = n; i < (n$ << 1); i += 1)
+{
+	# This is the lower limit.
+	t1 = sqrt(1/(3*i))
+
+	l = length(i$)/2
+
+	print "i: ", i, "\n"
+	#print "l: ", l, "\n"
+
+	if (l$ != l)
+	{
+		# Limit between 2.4 and 3.
+		limit = 2.7 << (l$ * 2)
+		#print "limit: ", limit, "\n"
+
+		if (i >= limit)
+		{
+			t2 = 1/(i >> (l$)) * 2
+		}
+		else
+		{
+			t2 = 1/(i >> (l$))
+		}
+	}
+	else
+	{
+		# Limit between 3.8-ish and 4.8
+		limit = 4.3 << (l$ * 2 - 1)
+		#print "limit: ", limit, "\n"
+
+		if (i >= limit)
+		{
+			t2 = 1/(i >> (l$ - 1)) * 8
+		}
+		else
+		{
+			t2 = 1/(i >> (l$ - 1)) * 4
+		}
+	}
+
+	# This is the upper limit.
+	t3 = sqrt(5/(3*i))
+
+	# This is true when the guess is in between the limits.
+	good = (t1 < t2 && t2 < t3)
+
+	print t1, " < ", t2, " < ", t3, ": ", good, "\n"
+
+	# Error if we have a problem.
+	if (!good) sqrt(-1)
+}
+
+halt
diff --git a/scripts/sqrt_random.bc b/scripts/sqrt_random.bc
new file mode 100644
index 000000000000..ff08348f4977
--- /dev/null
+++ b/scripts/sqrt_random.bc
@@ -0,0 +1,129 @@
+#! /usr/bin/bc
+#
+# SPDX-License-Identifier: BSD-2-Clause
+#
+# Copyright (c) 2018-2023 Gavin D. Howard and contributors.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are met:
+#
+# * Redistributions of source code must retain the above copyright notice, this
+#   list of conditions and the following disclaimer.
+#
+# * Redistributions in binary form must reproduce the above copyright notice,
+#   this list of conditions and the following disclaimer in the documentation
+#   and/or other materials provided with the distribution.
+#
+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+# POSSIBILITY OF SUCH DAMAGE.
+#
+
+scale = 0
+
+bits = rand()
+
+# This extracts a bit and takes it out of the original value.
+#
+# Here, I am getting a bit to say whether we should have a value that is less
+# than 1.
+bits = divmod(bits, 2, negpow[])
+
+# Get a bit that will say whether the value should be an exact square.
+bits = divmod(bits, 2, square[])
+
+# See below. This is to help bias toward small numbers.
+pow = 4
+
+# I want to bias toward small numbers, so let's give a 50 percent chance to
+# values below 16 or so.
+bits = divmod(bits, 2, small[])
+
+# Let's keep raising the power limit by 2^4 when the bit is zero.
+while (!small[0])
+{
+	pow += 4
+	bits = divmod(bits, 2, small[])
+}
+
+limit = 2^pow
+
+# Okay, this is the starting number.
+num = irand(limit) + 1
+
+# Figure out if we should have (more) fractional digits.
+bits = divmod(bits, 2, extra_digits[])
+
+if (square[0])
+{
+	# Okay, I lied. If we need a perfect square, square now.
+	num *= num
+
+	# If we need extra digits, we need to multiply by an even power of 10.
+	if (extra_digits[0])
+	{
+		extra = (irand(8) + 1) * 2
+	}
+	else
+	{
+		extra = 0
+	}
+
+	# If we need a number less than 1, just take the inverse, which will still
+	# be a perfect square.
+	if (negpow[0])
+	{
+		scale = length(num) + 5
+		num = 1/num
+		scale = 0
+
+		num >>= extra
+	}
+	else
+	{
+		num <<= extra
+	}
+}
+else
+{
+	# Get this for later.
+	l = length(num)
+
+	# If we need extra digits.
+	if (extra_digits[0])
+	{
+		# Add up to 32 decimal places.
+		num += frand(irand(32) + 1)
+	}
+
+	# If we need a value less than 1...
+	if (negpow[0])
+	{
+		# Move right until the number is
+		num >>= l
+	}
+}
+
+bits = divmod(bits, 2, zero_scale[])
+
+# Do we want a zero scale?
+if (zero_scale[0])
+{
+	print "scale = 0\n"
+}
+else
+{
+	print "scale = 20\n"
+}
+
+print "sqrt(", num, ")\n"
+
+halt
diff --git a/scripts/sqrt_random.sh b/scripts/sqrt_random.sh
new file mode 100755
index 000000000000..694c72003192
--- /dev/null
+++ b/scripts/sqrt_random.sh
@@ -0,0 +1,77 @@
+#! /bin/sh
+#
+# SPDX-License-Identifier: BSD-2-Clause
+#
+# Copyright (c) 2018-2023 Gavin D. Howard and contributors.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are met:
+#
+# * Redistributions of source code must retain the above copyright notice, this
+#   list of conditions and the following disclaimer.
+#
+# * Redistributions in binary form must reproduce the above copyright notice,
+#   this list of conditions and the following disclaimer in the documentation
+#   and/or other materials provided with the distribution.
+#
+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+# POSSIBILITY OF SUCH DAMAGE.
+#
+
+scriptdir=$(dirname "$0")
+
+gnu=/usr/bin/bc
+gdh=/usr/local/bin/bc
+
+if [ "$#" -lt 1 ]; then
+	printf 'err: must provide path to new bc\n'
+	exit 1
+fi
+
+new="$1"
+shift
+
+unset BC_LINE_LENGTH && unset BC_ENV_ARGS
+
+gdh_fail_file="sqrt_fails.bc"
+new_fail_file="new_sqrt_fails.bc"
+
+rm -rf "$gdh_fail_file"
+rm -rf "$new_fail_file"
+
+while [ true ]; do
+
+	tst=$("$gdh" -l "$scriptdir/sqrt_random.bc")
+	err=$?
+
+	if [ "$err" -ne 0 ]; then
+		printf 'err: failed to create test\n'
+		exit 2
+	fi
+
+	good=$(printf '%s\n' "$tst" | "$gnu" -l)
+
+	gdh_out=$(printf '%s\n' "$tst" | "$gdh" -l)
+	new_out=$(printf '%s\n' "$tst" | "$new" -l)
+
+	gdh_good=$(printf '%s == %s\n' "$good" "$gdh_out" | "$gnu")
+	new_good=$(printf '%s == %s\n' "$good" "$new_out" | "$gnu")
+
+	if [ "$gdh_good" -eq 0 ]; then
+		printf '%s\n' "$tst" >> "$gdh_fail_file"
+	fi
+
+	if [ "$new_good" -eq 0 ]; then
+		printf '%s\n' "$tst" >> "$new_fail_file"
+	fi
+
+done