In-place vermenigvuldiging met geheel getal

Ik schrijf een programma (in C) waarin ik de macht van grote getallen probeer uit te rekenen in een zo kort mogelijke periode. De cijfers die ik vertegenwoordig als vectoren van cijfers, dus alle bewerkingen moeten met de hand worden geschreven.

Het programma zou veel sneller zijn zonder alle toewijzingen en deallocaties van tussenresultaten. Bestaat er een algoritme voor het doen van integere vermenigvuldiging, op zijn plaats ? Bijvoorbeeld de functie

void BigInt_Times(BigInt *a, const BigInt *b);

zou het resultaat van de vermenigvuldiging van a en b in a , plaatsen zonder een tussenwaarde te gebruiken .

4
@Macmade De vraag is deze: "Bestaat er een algoritme voor integere vermenigvuldiging, in-place?"; tot dusverre heb ik een functie geschreven die een gehele vermenigvuldiging doet, maar niet op zijn plaats; en een functie voor het berekenen van machten (met log (f) complexiteit, waarbij f de complexiteit van de vermenigvuldigingsfunctie is).
toegevoegd de auteur Paul Manta, de bron
@DourHighArch Leerproject.
toegevoegd de auteur Paul Manta, de bron
Dus wat is de vraag? En wat heb je tot nu toe geprobeerd?
toegevoegd de auteur Macmade, de bron
@Macmade: Bestaat er een algoritme voor integer vermenigvuldigen?
toegevoegd de auteur Ziyao Wei, de bron
Dit is het soort vraag dat redelijk eenvoudig te beantwoorden is, maar ik zou een white-board nodig hebben om dit te doen ...
toegevoegd de auteur Mysticial, de bron
Is er een reden waarom je dit schrijft in plaats van het gebruik van een van de vele bestaande, krachtige, geteste, gedocumenteerde, werkende nu bignum-bibliotheken die al voor C zijn geschreven?
toegevoegd de auteur Dour High Arch, de bron

4 antwoord

Welnu, het standaardalgoritme bestaat uit het vermenigvuldigen van elk cijfer (woord) van 'a' met elk cijfer van 'b' en het optellen daarvan op de juiste plaatsen in het resultaat. Het i-de cijfer van a gaat dus in elk cijfer van i naar i + n van het resultaat. Dus om dit 'op zijn plaats' te doen, moet je de outputcijfers van de meest significante tot de laagste berekenen. Dit is een beetje lastiger dan van de minste tot de meesten, maar niet veel ...

2
toegevoegd

Hier is muln() 2n (echt, n) door n = 2n interne vermenigvuldiging voor niet-getekende gehele getallen. U kunt het aanpassen om te werken met 32-bits of 64-bits "cijfers" in plaats van 8-bits. De modulo-operator blijft voor de duidelijkheid over.

muln2() is n by n = n in-place multiplication (as hinted here), also operating on 8-bit "digits".

#include 
#include 
#include 
#include 

typedef unsigned char uint8;
typedef unsigned short uint16;
#if UINT_MAX >= 0xFFFFFFFF
typedef unsigned uint32;
#else
typedef unsigned long uint32;
#endif
typedef unsigned uint;

void muln(uint8* dst/* n bytes + n extra bytes for product */,
          const uint8* src/* n bytes */,
          uint n)
{
  uint c1, c2;

  memset(dst + n, 0, n);

  for (c1 = 0; c1 < n; c1++)
  {
    uint8 carry = 0;

    for (c2 = 0; c2 < n; c2++)
    {
      uint16 p = dst[c1] * src[c2] + carry + dst[(c1 + n + c2) % (2 * n)];
      dst[(c1 + n + c2) % (2 * n)] = (uint8)(p & 0xFF);
      carry = (uint8)(p >> 8);
    }

    dst[c1] = carry;
  }

  for (c1 = 0; c1 < n; c1++)
  {
    uint8 t = dst[c1];
    dst[c1] = dst[n + c1];
    dst[n + c1] = t;
  }
}

void muln2(uint8* dst/* n bytes */,
           const uint8* src/* n bytes */,
           uint n)
{
  uint c1, c2;

  if (n >= 0xFFFF) abort();

  for (c1 = n - 1; c1 != ~0u; c1--)
  {
    uint16 s = 0;
    uint32 p = 0;//p must be able to store ceil(log2(n))+2*8 bits

    for (c2 = c1; c2 != ~0u; c2--)
    {
      p += dst[c2] * src[c1 - c2];
    }

    dst[c1] = (uint8)(p & 0xFF);

    for (c2 = c1 + 1; c2 < n; c2++)
    {
      p >>= 8;
      s += dst[c2] + (uint8)(p & 0xFF);
      dst[c2] = (uint8)(s & 0xFF);
      s >>= 8;
    }
  }
}

int main(void)
{
  uint8 a[4] = { 0xFF, 0xFF, 0x00, 0x00 };
  uint8 b[2] = { 0xFF, 0xFF };

  printf("0x%02X%02X * 0x%02X%02X = ", a[1], a[0], b[1], b[0]);
  muln(a, b, 2);
  printf("0x%02X%02X%02X%02X\n", a[3], a[2], a[1], a[0]);

  a[0] = -2; a[1] = -1;
  b[0] = -3; b[1] = -1;
  printf("0x%02X%02X * 0x%02X%02X = ", a[1], a[0], b[1], b[0]);
  muln2(a, b, 2);
  printf("0x%02X%02X\n", a[1], a[0]);

  return 0;
}

Output:

0xFFFF * 0xFFFF = 0xFFFE0001
0xFFFE * 0xFFFD = 0x0006

Ik denk dat dit het beste is dat we ter plekke kunnen doen. Een ding dat ik niet leuk vind aan muln2() is dat het grotere tussenproducten moet verzamelen en dan een grotere carry moet verspreiden.

2
toegevoegd

Het klinkt niet alsof je echt een algoritme nodig hebt. Integendeel, u moet de functies van de taal beter gebruiken.

Waarom creëer je niet alleen die functie die je hebt aangegeven in je antwoord? Gebruik het en geniet ervan! (De functie zou waarschijnlijk resulteren in het retourneren van een verwijzing naar a als resultaat.)

0
toegevoegd

Typisch variëren de grote int-representaties in lengte afhankelijk van de weergegeven waarde; in het algemeen zal het resultaat langer zijn dan elke operand. In het bijzonder is voor vermenigvuldiging de grootte van de resulterende representatie ruwweg de som van de groottes van de argumenten.

Als u zeker weet dat geheugenbeheer echt het knelpunt is voor uw specifieke platform, kunt u overwegen een multiply-functie te implementeren die een derde waarde bijwerkt. In termen van je prototype in C-stijl functie hierboven:

void BigInt_Times_Update(const BigInt* a, const BigInt* b, BigInt* target);

That way, you can handle memory management in the same way C++ std::vector<> containers do: your update target only needs to reallocate its heap data when the existing size is too small.

0
toegevoegd
Ik heb al iets als de functie die je hebt voorgesteld (behalve dat het de waarde retourneert). Ook heb ik een beperking om alleen C-functies te gebruiken.
toegevoegd de auteur Paul Manta, de bron
Het was niet mijn bedoeling om gebruik std: vector <>. Ik bedoelde dat, als je functies hebt die je BigInt bijwerken (in plaats van een nieuwe te retourneren), je het heap-toegewezen geheugen kunt behouden in plaats van het opnieuw toe te wijzen, zolang je maar niet meer ruimte nodig hebt. Dit is hoe std :: vector <> zijn dynamische toewijzing doet; Ik stelde voor dat je het voorbeeld volgt ...
toegevoegd de auteur comingstorm, de bron
Ik heb mijn antwoord bewerkt; neem alsjeblieft een kijkje en kijk of het duidelijker is.
toegevoegd de auteur comingstorm, de bron