Korrigeringsmetod för att få bättre noggrannhet - varför fungerar den?

Den första biten (innan användaren börjar prata om powers of 2) är väl ganska rakt fram: du räknar hur många counts (vilka ska motsvara 1 sekund) du får på 5 minuter, dividerar resultatet på 5 och får hur många counts det går på en minut (i exemplet 58)? Då vet du att en count egentligen är 60/58 sekunder och kan anpassa din tidtagning 

Hondel skrev:

Den första biten (innan användaren börjar prata om powers of 2) är väl ganska rakt fram: du räknar hur många counts (vilka ska motsvara 1 sekund) du får på 5 minuter, dividerar resultatet på 5 och får hur många counts det går på en minut (i exemplet 58)? Då vet du att en count egentligen är 60/58 sekunder och kan anpassa din tidtagning 

Ah, det är jag helt med på! Jag är helt med på hur jag ska göra. Jag är bara intresserad av det jag skrev i citatet nedan;

Jag vill dels förstå varför vi får bättre noggrannhet när vi använder oss av powers av 2. Dessutom vill jag gärna veta - betyder "general technique" att det här är något känt koncept jag kan läsa på om online? Jag hittar fixed-point arithmetic vilket känns lite semirelevant.

Inser också att även om jag skriver "division" och "multiplikation" i OP så är det ju i praktiken bitshifting det kommer handla om.

Med brasklappen att jag aldrig prövat på något sånt här:

Vad jag kan se tycks metoden egentligen gå ut på att multiplicera talet med ett större tal innan man gör division, vilket borde göra så att felmarginalen blir mindre om vi förutsätter att man avrundar resultatet efter divisionen.

Att man sedan multiplicerar med 2^{[ett tal]} beror väl på att multiplikation och division med sådana tal är enkla i det binära talsystemen. Det är bara att man förskjuter alla ettorna och nollorna som utgör talet [ett tal] steg åt höger eller vänster då man dividerar eller multiplicerar. Hur man gör detta på elkretsnivå vet jag dock inte.

Hela grejen verkar handla om att avrunda korrektionsfaktorn till ett tal på formen p/2ⁿ

där p och n är heltal, och där divisionen nu kan kan implementeras med bit-shifting n steg istället för att implementera en sann divisionsalgoritm.

Detta är i praktiken hur flyttalsaritmetik implementeras så hela grejen handlar om att koda flyttalsaritmetik 'utan flyt'.

Hans post blev ganska förvirrande läsning eftersom han pratar om noggrannhet när hela grejen uppenbarligen är ett approximationsschema och att han använde  64 (n = 6) var helt godtyckligt. I princip blir metoden bättre ju större n vi men n = 6 kanske är motiverat av hårdvaruarkitekturen. Kanske för att gardera mot overflow där multiplikationen fyller upp hela datatypen innan vi bitshiftar ner vid divisionen?

Anywho, vi ingen hårdvarubegränsning kan vi i praktiken låta n vara det maximalt tillåtna värdet.

Hursomhelst; såhär förstår jag själva metoden:

Låt oss säga att vi gör en testmätning där  noggrann klocka mäter tid T och en dålig klocka mäter tid t.

Algebraiskt har vi

t = (t / T)*T

så om vi vill översätta verklig tid T till ekvivalent klocktid t  så kan vi multiplicera  med kalibreringsfaktorn.

C = (t/T)

C kan sparas med oändlig precision men det finns ingen anledning att göra det eftersom C ändå är en skattad snarare än exakt storhet och därmed inte känd med oändlig noggrannhet. Vi kan av aritmetikskäl välja att spara talet på formen 

C ~ p/2ⁿ

där p och n är heltal. För att finna p så kan vi (efter att vi valt n) ta C * 2ⁿ och avrunda till närmaste heltal. Vi får då ett fel på ungefär 1/2ⁿ

Vad är ett lämpligt n? Beror på men i praktiken finns det ingen anledning att låta n vara större än antalet binära siffor i T och t vid vår kalibreringsmätningen. Mer precist så medför off-by-1-error i t och T att relativa felet i kalibreringsfaktorn sannolikt är

e = 1/T + 1/t

Så länge T och t är av samma storleksordning så kan vi säga att T ~ t ~ 2ᴺ där N är log₂(T) avrundad till närmaste heltal i den aktuella. Så 

e ~ 2⁻ᴺ + 2⁻ᴺ = 2*2⁻ᴺ

Dvs det är i praktiken inte meningsfullt att spara kalibreringsfaktorn C med fler än N siffor. 

Exempel:

För

T = 300 ~ 2⁸

t = 288 ~ 2⁸

I exakt decimal form så har vi:

288/300 = 0.96000

och vårt förmodade absoluta fel är 

Δ(t/T) = e(t/T) = (288/300)*(1/288 + 1/300) = 0.007

>>Med en n = 6 (64)-approximation har vi

288/300 ~ 62/64 = 61/2⁶ = 0.953125

>>Med en n = 7 (128)-approximation har vi

288/300 ~ 123/128 = 123/2⁷ = 0.9609375

>>Med en n = 8 (256)-approximation har vi

288/300 ~ 246/256 = 246/2⁸ = 0.9609375

osv

Med större 2-potenser i basen får vi högre precision men tillslut så når vi under meningsfull noggrannhet.

@SeriousCephalopod, tack så jättemycket för ditt otroligt detaljerade och pedagogiska svar! Jag har inte haft möjlighet att kika på den här tråden förrän nu, men ditt svar var väldigt tydligt och lätt att hänga med i!

Det var ett tag sedan (ca 1 år sedan) jag läste numerisk analys (där vi gick igenom olika typer av felapproximation), så jag är lite osäker på hur du fick fram felets storlek:

Dels denna formel: 

Vi får då ett fel på ungefär 1/2ⁿ

och sen denna:

Mer precist så medför off-by-1-error i t och T att relativa felet i kalibreringsfaktorn sannolikt är

e = 1/T + 1/t

För denna formel, det här är en ren chansning, men är det för att:

$\frac {\partial C}{\partial t}=\frac 1 T$

$\frac {\partial C}{\partial T}=\frac {-t} T^2$

sen kan vi ju inte ha ett negativt fel då, så båda felen adderade borde bli

$\frac 1 T + \frac{t} T^2$

dividera med $C$ för att få relativfelet

$e=\frac 1 t + \frac T T^2 = \frac 1 t + \frac 1 T$

Men här jag inte ens nämnt ordet "off-by-1-error" när jag beräknar det relativa felet. Hur fick du fram formeln för $e$?

Slutligen vill jag gärna undvika att använda avrundning om jag kan. Låt mig förklara vad jag menar. Om vi kikar igen på inlägget jag nämnde i OP:

say 300 is perfect, we will multiply by 300*64 then divide by 64 (which is shifting not dividing)

so perfect gives 3840 =19200. 19200/64 is 300...well so what? Seems roundabout!!!

BUT NOW for 288 we have (5*N)/64 must equal 288, or N= 288*5/64= 3686.4 [store 3686]

Här antar jag att vi ska använda oss av heltalsdivision (eftersom användaren skriver "shifting")

Men här tolkar jag det som att jag ska använda mig av avrundning, alltså flyttalsaritmetik istället:

So if you set 5 minutes you do 5*3686 =18430. 18430/64 =287.96 (288 with rounding) now you get the needed final count (288) using your EEPROM cal value (3686) to get exactly 5 minutes (within at least 1 part in 288)

Det leder till att den implementationen som jag gjort just nu ser ut så här (tänkte att det var lättast att visa relevanta kodrader)

uint16_t calibrationValueH = readEEPROM(TIMER_CALIBRATION_EEPROM_ADDRESS_H);
uint8_t calibrationValueL = readEEPROM(TIMER_CALIBRATION_EEPROM_ADDRESS_L);
uint32_t calibrationValue = (calibrationValueH<<8) | (calibrationValueL);
float secondsToCountTo = MINUTES_TO_COUNT_TO * calibrationValue;
secondsToCountTo = round(secondsToCountTo / 64);

Det hade definitivt kännts mer clean att strunta i avrundningen, alltså att istället bara använda sig av bitshifts

uint16_t calibrationValueH = readEEPROM(TIMER_CALIBRATION_EEPROM_ADDRESS_H);
uint8_t calibrationValueL = readEEPROM(TIMER_CALIBRATION_EEPROM_ADDRESS_L);
uint32_t calibrationValue = (calibrationValueH<<8) | (calibrationValueL);
uint16_t secondsToCountTo = (MINUTES_TO_COUNT_TO * calibrationValue) >> 6;

Funderar på hur felet påverkas då. Att använda bitshiftning och inte avrundning i det sista steget ger väl ett fel $< 0.\bar 9$ iallafall?