C: schnelle Integer-Division Multiplikation mit 10^6

Mit entsprechend ausgestatteter Recheneinheit würde ich es mit x*1000000 
und x/1000000 versuchen.

Hab mir gerade mal den Spaß gemacht und GCC gefragt. Auf einem ARM läuft 
es auf eine Multipliation mit 1125899907 (mit 64 Bit Ergebnis) und 
anschließenden Shift um 50 Bits nach rechts raus.

M.m schrieb:
> Ich frag mich ob die Multiplikation durch Shifts schneller sei als
> einfach x*/10^6 zu schreiben?

Das hängt auch davon ab, ob der Compiler genau das selber macht.

M.m schrieb:
> Wolfgang schrieb:
>>
>> Und natürlich hängt es von deiner Hardware ab.
>
> Ich frag mich ob die Multiplikation durch Shifts schneller sei als
> einfach x*/10^6 zu schreiben?

Zumindest letzteres wird weder Speicher noch Laufzeit brauchen.
Das wird zur Compiletime zu einer Fehlermeldung.

Um Andrei Alexandrescu zu zitieren: "learn to know your hardware"

Multiplizieren kann man per HW 64x64 Bit in einem Takt (Chipfläche 
egal).
Division dagegen wird oft durch Muktiplikation mit dem Kehrwert 
erledigt, wobei der Kehrwert interativ ermittelt.
Wenn der Teiler aber fix ist (1000000), dann kann man (10^-6 << 
Wortbreite) multiplizieren und nur den oberen Teil des Ergebnisses 
benutzen. Und schon braucht mal nur den (hoffentlich Hw-)Multiplizierer.

M.m schrieb:
> Ich frag mich ob die Multiplikation durch Shifts schneller sei als
> einfach x*/10^6 zu schreiben?

Ja, das wird schneller gerechnet als du es schreiben kannst :-)

OLEK schrieb:
> Z.B. wie man eine Division implementiert für aneinander gereite
> ints/bytes.
> Da ist mir letztes nur die schriftliche Division eingefallen.

So ähnlich kann man es machen. Gibt da noch eine clevere Abschätzung die 
z.B. in The Art of Computer Programming 2 (Kapitel 4.3.1) erklärt wird.

... wenn ich jetzt noch eine Begründung erhalten könnte, was an meinem 
Post eine Löschung rechtfertigt?

Ok, unterschwellig war Der nicht Ohne ... gebe ich ja zu.
Zumindest im ersten Teil.

Im zweiten Teil, wo ich auf den kritisierten Ansatz eingehe, war aber 
weder böse, noch themenfern.

Soll das Niveau hier auf 'Ihr seid Alle inkompetent' runtergeregelt 
werden?

Zumindest wurden große Buchstaben und Satzzeichen benutzt, der deutschen 
Sprache also durchaus mächtig und durchaus bereit, halbwegs lesbare 
Posts abzugeben - trotzdem finde ich den Ton ... naja, ich schrieb ja 
bereits was dazu, Was wohl nicht sonderlich Gefallen gefunden hatte.

-----------------------------------------

Zurück zum kritisierten Ansatz, mit 5% Differenz einfach nur zu shiften:
Wenn ich damit Rechenzeit spare, kann ich zumindest in die Richtung 
überlegen.
Vll. fällt mir ja auch was ein, womit ich den Fehler im Vorfeld bereits 
positiv beeinflussen kann, daß ich eben näher an das geforderte Ergebnis 
durch shiften komme, als durch das Teilen durch 10^6.

MfG

@Mod
Sollte auch dieser Post Dir nicht sonderlich gefallen, kürze Ihn doch 
bitte entsprechend ein.

Patrick J. schrieb:
> Vll. fällt mir ja auch was ein, womit ich den Fehler im Vorfeld bereits
> positiv beeinflussen kann, daß ich eben näher an das geforderte Ergebnis
> durch shiften komme, als durch das Teilen durch 10^6.

Der Fehler kann auch durch aufsummieren/abziehen mehrerer geshiftenen 
Werte reduziert werden.

Achim S. schrieb:
> Ohne Multiplizierer sowas evt.?

Falls kein Barrellshifter vorhanden besser:

1

uint32 mul1000(uint32 x)

2

{

3

  uint32 y;

4

  // nur 10 Shifts

5

  x = x << 3;

6

  y = x << 7;

7

8

  /* inclusive lustiger Überläufe bei größeren x */

9

  y-=x;

10

  y-=x;

11

  y-=x;

12

  return y;

13

}

Aber falls es den in 32-Bit breit gibt, dann gibt es meist 
32x32-Multiplier

M.m schrieb:
> für value * 10^6 kann man ja 6 mal folgendes ausführen.
> value * 10 = (value << 3) + value << 1
>
> Für Division wie?

Wie oben irgendwo zu lesen war hat z.B. der ARM-GCC-Port solche C-Tricks 
selber drauf. Und der kennt dann auch die Ziel-HW besser als der 
generische C-Programmierer.

> Für Division wie?
Der nimmt dann schlicht den (fixen) Kehrwert, skaliert auf max. 
Genauigkeit für die vorhandene Ergebnisbreite, multipliziert und schiebt 
die Skalierung wieder zurück:

sebi_s schreibt:
> Hab mir gerade mal den Spaß gemacht und GCC gefragt.
> Auf einem ARM läuft es auf eine Multipliation mit 1125899907
> (mit 64 Bit Ergebnis) und anschließenden Shift um
> 50 Bits nach rechts raus.
also   x 112569907 / 2^50
was ziemlich genau 1/1000000 ist.
Und das macht der Compiler. Jedesmal auf den konkreten Divisor 
optimiert. In wenigen Sekunden.

Es macht heute mehr Sinn, dem Compiler konkret zu sagen, was er tun 
soll, und nicht wie er es machen soll.

Patrick J. schrieb:
> ... wenn ich jetzt noch eine Begründung erhalten könnte, was an meinem
> Post eine Löschung rechtfertigt?
Weil du in diesem Post auf einen Troll reagiert hast. Und sonst 
eigentlich nichts zur Sache drin stand...

> @Mod
> Sollte auch dieser Post Dir nicht sonderlich gefallen, kürze Ihn doch
> bitte entsprechend ein.
Im üblichen Fall werden Posts nicht auf Byteebene bearbeitet. 
Bestenfalls dann, wenn da zwar eine (allgemeine, unterschwellige) 
Beleidigung und sonst neue Informationen drin stehen, wird nur 
partiell gelöscht.

>Carl Drexler..
>Es macht heute mehr Sinn, dem Compiler konkret zu sagen, was er tun
soll, und nicht wie er es machen soll.

Ja und nein. Wenn man mit 5% Fehler leben kann, daher 20 mal schieben 
reicht verglichen mit was auch immer der Compiler wirres macht...

Die 5% Fehler kann ich mir zB fuer eine Strom-Status Anzeige leisen, 
fuer eine Temperaturanzeige zu einer Temperaturregelung eher nicht.

Sapperlot W. schrieb:
>>Carl Drexler..
>>Es macht heute mehr Sinn, dem Compiler konkret zu sagen, was er tun
> soll, und nicht wie er es machen soll.
>
> Ja und nein. Wenn man mit 5% Fehler leben kann, daher 20 mal schieben
> reicht verglichen mit was auch immer der Compiler wirres macht...
>
> Die 5% Fehler kann ich mir zB fuer eine Strom-Status Anzeige leisen,
> fuer eine Temperaturanzeige zu einer Temperaturregelung eher nicht.

In dem aufgeführten Beispiel liegt der Fehler nicht bei 5%, was man 
leicht nachrechnen kann, wenn man dazu in der Lage ist und falls man das 
nicht ist sollte man solche Dinge dem Compiler überlassen. Der wurde 
nämlich von Leuten geschrieben, die dazu in der Lage sind.

Possetitjel schrieb:
> M.m schrieb:
>
>> für value * 10^6 kann man ja 6 mal folgendes ausführen.
>> value * 10 = (value << 3) + value << 1
>
> Kann man.
>
> Man kann sich auch ueberlegen, dass 10^6 = 2^6 * 5^6 gilt.
> 5^6 ist aber 25^3. 25 ist 33 - 8; 33 ist 32 + 1.
>
> Also: value*25 = value*32 - value*8 + value
>
> Noch krasser ist, dass 5^3 = 125 = 128 - 3 gilt.
>
> Also: value*125 = value*128 - value*4 + value
> Das machst Du zwei mal; anschlieszend mit 64
> malnehmen. Fertsch.

Solche Zerlegungen sollte doch der Compiler selber beherrschen (ok, 
vernünftiges Programmieren vorausgesetzt). Wenn jetzt Float verwendet 
wird sieht es wieder anders aus. Aber auch hier haben gute Controller 
FPUs, welche dann entsprechend genutzt werden können.

Bei FPGA und ASIC Design ist es natürlich von Vorteil, wenn man nicht 
nur den Taschenrechner bedienen, sondern solche Zerlegungen selber kann. 
Aber auch hier wird je nach verwendeten Busbreiten schon automatisch mit 
DSP Slices gearbeitet.