41C 37-byte prgm (excluding label and end)
timing 100: 13.00s 31'796
540: 1m 09.12s 918'168
1000: 2m 07.44s 3'145'520
pixels in a circle
------------------
observations:
- input parameters x and y are superfluous. We will assume a circle with centre (0,0)
- solution is symmetric in every quadrant. We'll count the pixels in quadrant 1 and multiply by four
- a pixel(x,y) is lit when (x-1)^2 + (y-1)^2 < r^2
Let's start by assuming all pixels of the quadrant are lit, and then determine which ones are dark,
as follows (take r=10 as an example):
1. determine the first dark pixel in the top row:
(m-1)^2 + (10-1)^2 >= 10^2
or
m = CEIL(sqrt(10^2 - 9^2) + 1) = 6
so p(x,10) are lit, x=1..5
p(x,10) are dark, x=6..10
then, because of symmetry, we know these 9 pixels are dark:
x x x x x . . . . .
x x x x x x x x x .
x x x x x x x x x .
x x x x x x x x x .
x x x x x x x x x .
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
2. determine the first dark pixel in the second row:
(m-1)^2 + (9-1)^2 >= 10^2
or
m = CEIL(sqrt(10^2 - 8^2) + 1) = 7
so p(x,9) are lit, x=1..6
p(x,9) are dark, x=7..10 - but 10 we knew already
and we can darken the following 7 pixels, too:
x x x x x . . . . .
x x x x x x . . . .
x x x x x x x x . .
x x x x x x x x . .
x x x x x x x x x .
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
3. determine first dark pixel on row three
(m-1)^2 + (8-1)^2 >= 10^2
or
m = CEIL(sqrt(10^2 - 7^2) + 1) = 9
this means (x,8) is dark for x=9..10, and we are done
in pseudocode this reads:
p := r^2;
y := r;
do
y := y - 1;
m := CEIL(sqrt(r^2 - y^2) + 1);
t := (m-y)*2 - 3;
if t<0 then p := p + t;
until t>=0;
41C 37-byte prgm (excluding label and end)
timing 100: 13.00s 31'796
540: 1m 09.12s 918'168
1000: 2m 07.44s 3'145'520
01*LBL"PX"
02 RDN
03 RDN
04 STO 03 -- y
05 X^2
06 STO 01 -- r^2
07 STO 02 -- p
08*LBL 02
09 RCL 01
10 RCL 03
11 1
12 -
13 STO 03
14 X^2
15 -
16 SQRT
17 INT
18 LASTX
19 FRC
20 X#0?
21 SIGN
22 + -- m
23 RCL 03
24 -
25 ST+ X
26 1
27 -
28 X<0?
29 ST+ 02
30 X<0?
31 GTO 02
32 RCL 02
33 4
34 *
35 END