~tleguern/krt

krt/sqrt.sh -rw-r--r-- 2.3 KiB
a9fd2be7Tristan Le Guern Settle on four part a month ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
fixed_nearest() {
	local i="$1"; shift
	if [ $# -eq 1 ]; then
		local input="$1"; shift
	else
		local input=./perfect_squares.txt
	fi
	local x=1

	if ! [ -f "$input" ]; then
		echo "sqrt: invalid input file" >&2
		exit 1
	fi
	set $(cat "$input")
	while ! [ "$i" -le "$2" ]; do
		x=$(( x + 1 ))
		shift
	done
	echo "$x"
}

dynamic_nearest() {
	local x=0
	local i="$1"

	while [ $i -gt 0 ]; do
		local j=1
		while [ "$j" -lt "$i" ]; do
			if [ $((j * j)) -eq "$i" ]; then
				x=$j
				break 2
			fi
			j=$(( j + 1 ))
		done
		i=$(( i - 1 ))
	done
	echo $x
}

newton() {
	local S="$1"; shift
	local x="$1"; shift
	if [ $# -ge 1 ]; then
		local maxsteps="$1"
	else
		local maxsteps=5
	fi
	local factor="${FACTOR:-1000}"
	local steps=1

	while [ "$steps" -lt "$maxsteps" ]; do
		local nextx=$(( x - (x * x / factor - S) * factor / (2 * x) ))
		if [ "$x" = "$nextx" ]; then
			break
		fi
		x="$nextx"
		#echo "$steps / $maxsteps" >&2
		steps=$(( steps + 1 ))
	done
	printf "%d\n" "$x"
}

heron() {
	local S="$1"; shift
	local x="$1"; shift
	if [ $# -ge 1 ]; then
		local maxsteps="$1"
	else
		local maxsteps=5
	fi
	local factor="${FACTOR:-1000}"
	local steps=1

	while [ "$steps" -lt "$maxsteps" ]; do
		local nextx=$(( (x + S * factor / x) / 2 ))
		if [ "$x" = "$nextx" ]; then
			break
		fi
		x="$nextx"
		#echo "$steps / $maxsteps" >&2
		steps=$(( steps + 1 ))
	done
	printf "%d\n" "$x"
}

bakhshali() {
	local S="$1"; shift
	local x="$1"; shift
	local factor="${FACTOR:-1000}"

	for steps in 1 2; do
		local a=$(( (S - x * x / factor) * factor / (2 * x) ))
		local b=$(( x + a ))
		local nextx=$(( b - (a * a / factor) * factor / (2 * b) ))
		x="$nextx"
	done
	printf "%d\n" "$x"
}

cheating_with_bc() {
	local S="$1"; shift
	local factor="${FACTOR:-1000}"
	local scale="$(printf "%d" $factor | tr -d '[1-9]' | wc -c)"

	local res="$(bc -l -e "scale=$scale; sqrt($S/$factor)*$factor" -e quit)"
	echo "$res" | cut -d '.' -f 1
}

# Example from wikipedia: sqrt(125348)
# nearest=$(fixed_nearest 125348)
# heron $((125348 * 1000)) $(( nearest * 1000 ))
# bakhshali $((125348 * 1000)) $(( nearest * 1000 ))
# newton $((125348 * 1000)) $(( nearest * 1000 ))

# Example: sqrt(5.160)
# nearest=$(fixed_nearest $(( 5160 / 1000 )))
# newton 5160 $(( nearest * 1000 ))
# heron 5160 $(( nearest * 1000 ))
# bakhshali 5160 $(( nearest * 1000 ))