Compute Mult, such that Signal ** Mult == Target, using a binary search.
Phil Pilgrim (PhiPi)
Posts: 23,514
A typical problem in signal processing is calibration, wherein you take a raw signal and multiply it by a scaling factor to get a calibrated value. Whether it's wind speed, air pressure, temperature, or a white-balanced color coordinate, the process is the same. The tricky part is computing the scaling factor from a a known signal reading.
In working with the ColorPAL, for example, doing a white balance is critical to getting the RGB figures the same when presented with a white target. In the past, I've taken the raw readings from a white target and divided them into $FF80 to get a correction factor:
sred = $FF80 / red sgrn = $FF80 / grn sblu = $FF80 / blu
Then, when I want a white-balanced reading, I do this:
red = red */ sred grn = grn */ sgrn blu = blu */ sblu
This works fine when you're normalizing white to be $FF (255) across all the RGB coordinates. But it's not fine if you want a larger range. In that case you want to use:
red = red ** sred grn = grn ** sgrn blu = blu ** sblu
But how to find the s--- values, when the target white value is, say, white? On a calculator they would be, for example:
sred = white * 65536 / red
But you can't do that computation directly on a BASIC Stamp.
Tracy Allen has solved this by writing a long division routine, which he describes here:
http://emesystems.com/OLDSITE/BS2math2.htm
I decided to go at it from a slightly different direction, using a binary search. Here's a program that implements that search and tests it:
' {$STAMP BS2PE}
' {$PBASIC 2.5}
mult VAR Word
signal VAR Word
targ VAR Word
x VAR Word
seed VAR Word
sumiter VAR Word
i VAR Nib
j VAR Byte
targ = 1000
seed = 6789
DEBUG " X M X**M Iter", CR
DEBUG "----- ----- ---- --", CR
FOR j = 1 TO 50
RANDOM seed
signal = seed ** 30000 + targ
GOSUB FindMultiplier
DEBUG DEC5 signal, " ", DEC5 mult, " ", DEC4 signal ** mult, " ", DEC2 15 - i, CR
sumiter = sumiter + 15 - i
NEXT
sumiter = sumiter / 5
DEBUG CR, "Average iterations: ", DEC sumiter / 10, ".", DEC sumiter // 10, CR
END
FindMultiplier:
mult = $8000 'Set multiplier to a middle value
FOR i = 14 TO 0 'Do 15 iterations.
x = mult ** signal 'Compute a trial value.
IF (x > targ) THEN 'If it's too big, subtract half the remaining distance from the multiplier.
mult = mult - (1 << i)
ELSEIF (x < targ) THEN 'If it's too small, add half the remaining distance to the multiplier.
mult = mult + (1 << i)
ELSE 'If it's spot on, quit.
EXIT
ENDIF
NEXT
RETURN
Here's the output:
X M X**M Iter ----- ----- ---- -- 12184 05384 1000 13 23626 02776 1000 13 18308 03580 1000 14 10746 06104 1000 13 02405 27264 1000 09 25099 02612 1000 14 21013 03120 1000 12 25208 02600 1000 13 26628 02462 1000 15 12598 05204 1000 14 10629 06168 1000 13 27791 02360 1000 13 29316 02236 1000 14 25131 02608 1000 12 09879 06640 1000 12 09242 07096 1000 13 25501 02572 1000 14 17490 03748 1000 14 04885 13424 1000 12 27407 02392 1000 13 14758 04444 1000 14 03763 17424 1000 12 02249 29152 1000 11 26403 02484 1000 14 24089 02722 1000 15 23559 02784 1000 11 20092 03264 1000 10 23457 02796 1000 14 15143 04328 1000 13 12090 05424 1000 12 22654 02894 1000 15 06156 10656 1000 11 07473 08776 1000 13 23697 02768 1000 12 19062 03440 1000 12 23883 02746 1000 15 09717 06748 1000 14 11618 05644 1000 14 01529 42880 1000 09 22311 02940 1000 14 02136 30688 1000 11 15891 04128 1000 11 05866 11176 1000 13 04504 14560 1000 11 20440 03208 1000 13 08093 08104 1000 13 15524 04224 1000 09 01570 41760 1000 11 09490 06912 1000 08 03519 18624 1000 10 Average iterations: 12.5
It seems to work, and I will be using it henceforth in a certain ColorPAL application that I've written for a customer.
-Phil
Comments
This is extremely clever and I may be trying it soon in the 32-bit space of Propeller projects.