Ich habe mal wieder eine Knobelaufgabe:
Ich habe eine Funktion, die für alle Eingabewerte korrekte Werte liefern
soll. Es ist eine Division mit großem Zähler und großem Nenner ( der
Nenner hat eine Größenordnung von 2^33, die Größenordnung des Zählers
sieht man ja ).
Das folgende einfache Programm funktioniert natürlich nicht für den
gesamten Wertebereich des Parameters:
1 |
|
2 | #define RATE1 250000
|
3 | #define RATE2 100000
|
4 |
|
5 | /** Skalierung auf 31 Bit
|
6 | *
|
7 | * delta_z = (a * L * 2)/(f_0 * f_1)
|
8 | *
|
9 | * @param[in] a_spss: 0...UINT32_MAX
|
10 | * @return delta_z 0...INT32_MAX */
|
11 | uint32_t prm_delta_z(uint32_t a_spss)
|
12 | {
|
13 | /* Der Zaehler läuft über ab a = UINT32_MAX/4; */
|
14 | uint64_t dVz = (uint64_t) a_spss * (1ULL<<32) * 2;
|
15 | uint64_t dVn = (uint64_t) RATE1 * RATE2;
|
16 |
|
17 | /* Läuft ueber ab a = UINT32_MAX/4 - X */
|
18 | uint64_t dV = (dVz + (dVn/2))/dVn;
|
19 |
|
20 | /* Ergebnis saettigen auf 2^31-1 */
|
21 | if( dV >= INT32_MAX )
|
22 | {
|
23 | dV = INT32_MAX;
|
24 | }
|
25 | return dV;
|
26 | }
|
Um den Ausgangswert allein von der Formel im erlaubten Wertebereich zu
erhalten, darf der Eingangswert bis zu ca. 2,5e9, also ca. UINT31_MAX
betragen. Aber der 64-Bit-Zwischenwert läuft schon deutlich früher über.
Jetzt knobele ich gerade daran, wie ich diese Funktion am geschicktesten
in ihrem kompletten Wertebereich gültig bekomme.
Anforderungen an die Geschwindigkeit gibt es keine. Meine Version des
ARM-GCCs kennt keine 128-Bit-Variablen.
Die einfachste Lösung, die mir spontan einfällt, wäre von den
Nenner-Konstanten den Primfaktor 2 solange abzuspalten, wie es möglich
ist. Für die genannten Konstanten wären das immerhin 2^7. Also so:
1 | uint32_t prm_delta_z(uint32_t a_spss)
|
2 | {
|
3 | /* Der Zaehler läuft über ab a = UINT32_MAX/4; */
|
4 | //uint64_t dVz = (uint64_t) a_spss * (1ULL<<32) * 2;
|
5 | //uint64_t dVn = (uint64_t) RATE1 * RATE2;
|
6 |
|
7 | /* Konstanten Teil von Zaehler und Nenner aufstellen und durch 2 kuerzen */
|
8 | uint64_t dVz = (uint64_t) (1ULL<<32) * 2;
|
9 | uint64_t dVn = (uint64_t) RATE1 * RATE2;
|
10 |
|
11 | while( !(dVz&1) && !(dVn&1) )
|
12 | {
|
13 | dVz /= 2;
|
14 | dVn /= 2;
|
15 | }
|
16 |
|
17 | dVz *= a_spss;
|
18 |
|
19 |
|
20 | uint64_t dV = (dVz + (dVn/2))/dVn;
|
21 |
|
22 | /* Ergebnis saettigen auf 2^31-1 */
|
23 | if( dV >= INT32_MAX )
|
24 | {
|
25 | dV = INT32_MAX;
|
26 | }
|
27 |
|
28 | return dV;
|
29 | }
|
Aber geht es eleganter und allgemeingültiger?
Thread beobachten
Seitenaufteilung abschalten