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
120
121
122
|
/* Copyright 2012 Kevin Ryde
This file is part of Math-PlanePath.
Math-PlanePath is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
Math-PlanePath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License along
with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
*/
#include <math.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long my_unsigned;
typedef long long my_signed;
#define MY_SIGNED_ABS llabs
#define HYPOT_LIMIT 0x7FFFFFFF
char *
binary (unsigned long long n)
{
static char str[sizeof(n)*8+1];
int pos = sizeof(str)-1;
do {
str[pos] = (n&1)+'0';
n >>= 1;
pos--;
} while (n);
return str+pos+1;
}
int
main (void)
{
int level;
for (level = 0; level < 8*sizeof(my_unsigned)-1; level++) {
unsigned long long min_h = ~0ULL;
my_unsigned min_n = 0;
my_signed min_x = 0;
my_signed min_y = 0;
{
my_unsigned lo = (my_unsigned)1 << level;
my_unsigned hi = (my_unsigned)1 << (level+1);
/* printf ("%2d lo=%lu hi=%lu\n", level, lo, hi); */
my_unsigned n;
for (n = lo; n < hi; n++) {
my_signed x = 0;
my_signed y = 0;
my_signed bx = 1;
my_signed by = 0;
my_unsigned bits;
for (bits = n; bits != 0; bits >>= 1) {
if (bits & 1) {
x += bx;
y += by;
/* (bx,by) * i, rotate +90 */
my_signed new_bx = -by;
my_signed new_by = bx;
bx = new_bx;
by = new_by;
}
/* (bx,by) * (i+1) */
my_signed new_bx = bx-by;
my_signed new_by = bx+by;
bx = new_bx;
by = new_by;
}
unsigned long long abs_x = MY_SIGNED_ABS(x);
unsigned long long abs_y = MY_SIGNED_ABS(y);
if (abs_x > HYPOT_LIMIT
|| abs_y > HYPOT_LIMIT) {
continue;
}
unsigned long long h = abs_x*abs_x + abs_y*abs_y;
/* printf ("%2d %lu %Ld,%Ld %LX\n", level, n, x,y, h); */
if (h < min_h) {
min_h = h;
min_n = n;
min_x = abs_x;
min_y = abs_y;
}
}
}
/* printf ("%lX %Ld,%Ld %s\n", min_n, min_x,min_y, */
/* binary(min_h)); */
printf ("%2d", level);
char *binary_str = binary(min_h);
int binary_len = strlen(binary_str);
printf (" %s [%d]", binary(min_h), binary_len);
printf ("\n");
/* printf ("\n"); */
}
return 0;
}
|
