Divisions-Algorithmus selbst schreiben... / Aber wie?


20.12.2023, 17:38

ChatGPT schlägt den da vor (ist der überhaupt korrekt? ChatGPT verarscht mich total oft und knickt dann auf Nachfrage sofort diametral ein...):

void divmod(u32 N, u32 D, u32& Q, u32& R) { s8 i;
  if (D) for (Q=0, R=0, i=31; i>=0; i--) {
    R <<= 1;
    R |= (N >> i) & 1;
    if (R >= D) {
      R -= D;
      Q |= (1U << i);
    }
  } else Q = R = -1UL;
}

25.12.2023, 19:17

also das da läuft mit GCC auf nem J5040 (-O3 -march=goldmont) für divmodA(meins) 6,2sec und für divmodB(ChatGPT) 12,7sec... korrekt scheinen beide zu sein (laut Monte-Carlo-Simulation...)...

#include <stdlib.h>
#include <unistd.h>
#include <stdint.h>
typedef uint8_t   u8;
typedef uint16_t  u16;
typedef uint32_t  u32;
typedef uint64_t  u64;

u64 divmodA(u32 N, u32 D, u32 B) {
  for (; N>D && !(D&(((1U<<8)-1U)<<24)); B<<=8)
    { u32 nD=D<<8; if (N<nD) break; D=nD; }
  for (; N>D && !(D&(1U<<31)); B<<=1)
    { u32 nD=D<<1; if (N<nD) break; D=nD; }
  u32 R; for (R=0; N!=0 && B!=0; D>>=1,  B>>=1)
    if (N>=D) { N-=D; R|=B; }
  return (((u64)N)<<32) | R;
}

void divmodB(u32 N, u32 D, u32& Q, u32& R) { s32 i;
  if (D) for (Q=0, R=0, i=31; i>=0; i--) {
    R <<= 1;
    R |= (N >> i) & 1;
    if (R >= D) {
      R -= D;
      Q |= (1U << i);
    }
  } else Q = R = -1U;
}

u32 rnd(u32& R, u32& r, u32 l) {
    u32 N = 0;
    while (l > 0) {
        if (!r) { r=31; R=random(); }
        u32 L=l; if (L>r) L=r; l-=L; r-=L;
        N<<=L; N|=(R&((1U<<L)-1)); R>>=L;
    }
    return N;
}

int main() {
    u32 seed; read(0,&seed,sizeof(seed)); srandom(seed);
    const u32 C = 32U*32U*100U*1000U;
    u32 S = 0;
    u32 R=0, r=0;
    for (u32 i=C; i>0; i--) {
        u8 lN=i%32, lD=1+(i/32)%31;
        u32 N = rnd(R,r,lN);
        u32 D; if (lD==1) D=1; else while (!(D=rnd(R,r,lD)));
        u64 RA = divmodA(N,D,1); S+=RA; S+=(RA>>32);
        //u32 Q,R; divmodB(N,D,Q,R); S+=Q; S+=R;
    }
    return S;
}

1 Antwort

Vom Fragesteller als hilfreich ausgezeichnet
Und GCC will ganz viele 32bit instructions aus seiner libgcc.a verwenden, die der STM32G030 überhaupt gar nicht verstehen kann...

Dann stimmt was an deinen GCC-Einstellungen nicht... Normalerweise sollten auch nur Bibliotheken geladen werden, die kompatibel zu einem Prozessor sind. Es wäre doch sehr sonderbar, wenn in gewöhnlichem C keine Division möglich wäre... Notfalls müsste es doch sogar Bibliotheken für ARM Thumb geben...

Das andere: Wenn Chat-GPT einen Algorithmus vorschlägt, wirst du ihn auch irgendwo finden... 32 Zyklen bei 32 Bit klingt für mich plausibel. Wäre bei Multiplikation auch so...

Deinen Quelltext finde ich nicht gut lesbar.

LUKEars 
Fragesteller
 15.12.2023, 09:07

ist mein Algorithmus denn korrekt? oder ist die Lesbarkeit so schlimm, dass man das gar nich mehr beurteilen mag...? lol

0
tunik123  15.12.2023, 09:23
Deinen Quelltext finde ich nicht gut lesbar.

Das ist aber noch sehr verharmlosend ausgedrückt.

Das ist ein Kandidat für den Obfuscated C Code Contest.

0
LUKEars 
Fragesteller
 16.12.2023, 07:07
@tunik123

gar nich.... ich find das total einfach... praktisch Grundschul-Niveau... ihr hört euch an wie ChatGPT... lol

0