C: schnelle Integer-Division Multiplikation mit 10^6

[M.m (Gast)]

Hallo,

wie teilt/multipliziert ich am schnellsten in C einen Integer 32Bit mit 
1000000?

Vielen Dank.

[M.m (Gast)]

Hallo,

wie teile/multipliziere ich am schnellsten in C einen Integer 32Bit mit 
1000000?

Vielen Dank.

[(prx) A. K. (prx)]

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

[holger (Gast)]

>wie teile/multipliziere ich am schnellsten in C einen Integer 32Bit mit >1000000?

Wert / 1000000
Wert * 1000000

[Wolfgang (Gast)]

M.m schrieb:
> wie teilt/multipliziert ich am schnellsten in C einen Integer 32Bit mit
> 1000000?

Du wirst du entscheiden müssen.
Multiplikation und Division können sehr unterschiedlich lange brauchen.

Und natürlich hängt es von deiner Hardware ab.

[M.m (Gast)]

Wolfgang schrieb:
> M.m schrieb:
>> wie teilt/multipliziert ich am schnellsten in C einen Integer 32Bit mit
>> 1000000?
>
> Du wirst du entscheiden müssen.
> Multiplikation und Division können sehr unterschiedlich lange brauchen.
>
> 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?

[Sebastian V. (sebi_s)]

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.

[(prx) A. K. (prx)]

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.

[OLEK (Gast)]

auch wenn es ein troll ist.

Hab dazu auch mal ne frage.

Kann mir jemand ein Buch empfehlen, welches so die gängigen/bekannten 
Algos für so die verschiedenen Rechnungen enthält?

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

Oder z.B. der Cordic und was weis ich was es noch alles gibt.

Float nach String etc.

[Trampel (Gast)]

Allenfalls kann man sich ueberlegen ob die Zahl wirklich genau 1'000'000 
sein muss, oder ob 1'048'576, dh 5% mehr auch passen wuerde. Das waere 
dann 2^20, resp schieben um 20 bit nach links oder rechts.

[Carl D. (jcw2)]

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.

[Johann L. (gjlayde)]

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 :-)

[Sebastian V. (sebi_s)]

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.

[Wolfgang (Gast)]

MaWin schrieb im Beitrag #4966145:
> Hier läuft ein Genie nach dem anderen auf. Unglaublich diese geballte
> Inkompetenz.

Es haben sich schon Leute halb tot gerechnet, um Messdaten auszuwerten, 
die mit einer Genauigkeit von schlechter als ein Promille gemessen 
wurden. Wenn der TO vernünftige Randbedingungen angeben würde, ...

Garbage in - Garbage out

[Patrick J. (ho-bit-hun-ter)]

... 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.

[A. S. (Gast)]

Ohne Multiplizierer sowas evt.?

uint32 mul1000(uint32 x)
{
uint32 y = x<<10;
  
 
   x<<=3;
   /* inclusive lustiger Überläufe bei größeren x */
   y-=x;
   y-=x;
   y-=x;
   return y;
}


main()
{
uint32 x=getAnyX();


   x=mul1000(x);
   x=mul1000(x);

}

[Joe F. (easylife)]

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.

[Carl D. (jcw2)]

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

Falls kein Barrellshifter vorhanden besser:

uint32 mul1000(uint32 x)
{
  uint32 y;
  // nur 10 Shifts
  x = x << 3;
  y = x << 7;

  /* inclusive lustiger Überläufe bei größeren x */
  y-=x;
  y-=x;
  y-=x;
  return y;
}

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

[M.m (Gast)]

für value * 10^6 kann man ja 6 mal folgendes ausführen.
value * 10 = (value << 3) + value << 1

Für Division wie?

[Possetitjel (Gast)]

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.

[Carl D. (jcw2)]

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.

[A. S. (Gast)]

falls der µC nur 16-Bit-multipliz-/dividiert, ggf. zuerst mit 
(1000.000/2^6) multiplizieren und 6 mal schieben....

[Dieter (Gast)]

OLEK schrieb:
> Kann mir jemand ein Buch empfehlen, welches so die gängigen/bekannten
> Algos für so die verschiedenen Rechnungen enthält?

https://www.amazon.de/dp/B00CMNTKZ4/

Das haben viele Hochschulen in elektronischer Form oder auch Google 
sollte entsprechende Resultate für einen kurzen Blick in das Buch 
liefern...

Ggf. steht in folgendem Buch auch etwas drin, wobei 10^6 eher relativ 
niedrig ist, im fxtbook sind aber viele low level Geschichten drin mit 
denen man viel optimieren kann, ggf. findet sich da etwas für deine 
Problematik (wobei die eingeworfene Magic Number Lösung doch schon 
relativ elegant ist).

http://jjj.de/fxt/fxtbook.pdf#section.29.1
http://jjj.de/fxt/fxtpage.html
http://jjj.de/fxt/fxtbook.pdf

Fun fact: Der Downloadlink dieses Autors selbst ist bei Google höher 
gerankt als der von Händlern. Mich beschleicht da so das Gefühl, dass 
der Verlag da kaum Profit mit macht.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

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.

[Pandur S. (jetztnicht)]

>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.

[Carl D. (jcw2)]

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.

[Patrick B. (p51d)]

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.