3. große Zahlen

große Zahlen

  • ?

    Hi,

    2er Potenzen kann man durch verdoppeln ausrechnen. D.h. die zu potenzierende Zahl wird immer mit sich selbst addiert. Der Taschenrechner bc scheint das aber noch anders zu machen, der benutzt auch nicht gmp. Addition ist recht einfach, das sieht so aus wie eine schriftliche Addition, die man aus der Schule kennt - mit der Subtraktion und Multiplikation ist es genauso. Dann wird man aber leider feststellen müssen, daß die Schulmultiplikation dermaßen langsam ist, daß man etwas anderes braucht. Da gibt es dann z.B. die Karatsubamultiplikation, die schon ganz nett ist, aber immer noch langsam. Leute, die seitenlange Primzahlen berechnen, benutzen die sog. schnellen Fouriertransformationen (fft), dafür braucht man aber komplexe Zahlen, was eine Implementation ziemlich schwer macht. Oder du machst das so wie Gary, mit Bitshifting (@Gary hab deinen Algorithmus nicht testen können, da fehlt irgendeine Headerdatei).
    Achja, was es an schnellen Divisionen gibt, weiß ich leider nicht. Habe bisher nur die Bauernmethode und Schuldivision ausgetestet, waren aber beide ziemlich langsam.

    Hier findest du einen Ansatz mit ein paar Funktionen (auch Karatsuba, keine Division) in C:
    http://mitglied.lycos.de/cprokt/largeint.rar <edit>mit "Ziel speichern unter" speichern</edit>

    [ Dieser Beitrag wurde am 27.12.2002 um 08:53 Uhr von Doktor Prokt editiert. ]

    0
  • G

    hi,
    @ Doktor Prokt: Wenn ich in der Konsole unrar aufrufe, sagt er mir, dass in allen drei Dateien unbekannt Funtkionen vorhanden sind und entpackt nichts.
    Unter ark sagt er mir, dass ich das Programm rar nicht installiert habe, aber ich kann kein Packet o.ä. von rar finden. Hast du die nicht als Textdateien oder so?

    Tschau Gartenzwerg

    0
  • G

    @Doktor Prokt:
    Wie heißt die Datei?

    0
  • ?

    @Gartenzwerg
    Hm, ich habs auch nicht mehr entzippen können, habe es "damals" noch unter Windows geschrieben. Ich hab aber die einzelnen Dateien noch auf irgendeiner CD, ich such sie gleich mal.

    @Gary
    bitalg.hpp, hab sie aber gerade im nächsten Beitrag gefunden 😃
    ich werd morgen mal vergleichen.

    0
  • ?

    So, habs gefunden. Ich hab übrigens die verpönte Basis 10 genommen, wollte es hinterher noch umändern, aber mir fehlte die Motivation.
    Die Schuldivision funktioniert übrigens auch nicht. Ich habs zwar in einer neueren Version in C++ geschafft, doch da fehlte mir dann, nachdem ich festgestellt hab, daß die Schuldivision noch langsamer als die Bauernmethode ist, auch die Motivatoin, das zu Ende zu bringen 😃

    // largeint.h
#ifndef _LARGEINT_
#define _LARGEINT_

#include <stddef.h>

typedef signed short digit;
typedef enum { FALSE, TRUE } BOOL;

extern void cons (digit* num, const char* str);
extern void add (digit* sum, const digit* addend1, const digit* addend2, size_t len);
extern void subtract (digit* diff, const digit* minuend, const digit* subtrahend, size_t len);
extern void school_boy_multiply (digit* prod, const digit* factor1, const digit* factor2, size_t len);
extern void karatsuba (digit* prod, const digit* factor1, const digit* factor2, size_t len);
extern void school_boy_division (digit* quotient, const digit* dividend, unsigned int len1,
                 const digit* divisor, unsigned int len2);
extern BOOL is_greater (const digit* obj1, const digit* obj2, size_t len);
extern size_t digits (const digit* num);
extern void print (const digit* num, size_t len);

#endif // _LARGEINT_

// largeint.cpp
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include "largeint.h"

void cons (digit* num, const char* str)
{
    int i, j;
    for (i = strlen(str) - 1, j = 0; i >= 0; i--, j++)
    {
    if (isdigit(str[j]))
        num[i] = str[j] - '0';
    }
}

void add (digit* sum, const digit* addend1, const digit* addend2, unsigned int len)
{
    unsigned int i;
    int curr_digit, buf = 0;
    for (i = 0; i < len; i++)
    {
    curr_digit = addend1[i] + addend2[i] + buf;
    if (curr_digit >= 10)
        curr_digit -= 10, buf = 1;
    else
        buf = 0;
    sum[i] = curr_digit;
    }
    if (buf)
    sum[i] += buf;
}

void subtract (digit* diff, const digit* minuend, const digit* subtrahend, unsigned int len)
{
    unsigned int i;
    int curr_digit, buf = 0;
    for (i = 0; i < len; i++)
    {
    curr_digit = minuend[i] - (subtrahend[i] + buf) ;
    if (curr_digit < 0)
        curr_digit += 10, buf = 1;
    else
        buf = 0;
    diff[i] = curr_digit;
    }
}

void school_boy_multiplication (digit* prod, const digit* factor1, unsigned int len1,
                const digit* factor2, unsigned int len2)
{
    unsigned int i,j;
    int curr_digit, old_digit, buf = 0;
    digit* ptr_buf = calloc(len1 + len2, sizeof(digit));
    for (j = 0; j < len2; j++)
    {
    for (i = 0; i < len1; i++)
    {
        curr_digit = factor1[i] * factor2[j] + buf;
        if (curr_digit >= 10)
        {
        old_digit = curr_digit;
        curr_digit -= (old_digit / 10) * 10;
        buf = old_digit / 10;
        }
        else
        buf = 0;
        ptr_buf[j + i] = curr_digit;
    }
    if (buf)
        ptr_buf[j + i] = buf;
    add(prod,prod,ptr_buf,len1 + len2);
    ptr_buf[j] = 0;
    buf = 0;
    }
}

void karatsuba (digit* prod, const digit* factor1, const digit* factor2, size_t len)
{
    digit* buf = calloc(2 * len, sizeof(digit));
    BOOL s1, s2;
    if (len <= 1)
       school_boy_multiplication(prod,factor1,len,factor2,len);
    else
    {
    karatsuba(prod + len, factor1 + (len / 2), factor2 + (len / 2), len / 2);
    karatsuba(prod, factor1, factor2, len / 2);
    add(buf, prod + len, prod, len);
    add(prod + (len / 2), prod + (len / 2), buf, len + (len / 2));
    memset(buf, 0, 2 * len * sizeof(digit));
    if (is_greater(factor1, factor1 + (len / 2), len / 2))
        subtract(buf, factor1, factor1 + (len / 2), len / 2), s1 = TRUE;
    else
        subtract(buf, factor1 + (len / 2), factor1, len / 2), s1 = FALSE;
    if (is_greater(factor2 + (len / 2), factor2, len / 2))
        subtract(buf + (len / 2), factor2 + (len / 2), factor2, len / 2), s2 = TRUE;
    else
        subtract(buf + (len / 2), factor2, factor2 + (len / 2), len / 2), s2 = FALSE;
    karatsuba(buf + len, buf, buf + (len / 2), len / 2);
        memset(buf, 0, len * sizeof(digit));
    if (s1 == s2)
        add(prod + (len / 2), prod + (len / 2), buf + len, len);
    else
        subtract(prod + (len / 2), prod + (len / 2), buf + len, len);
    }
    return;
}

void school_boy_division (digit* quotient, const digit* dividend, unsigned int len1,
              const digit* divisor, unsigned int len2)
{
    int tmp1, tmp2, dd_i = len1 - 1, buf_i = 0, buf_len = len2 + 1;
    digit* buf = calloc(buf_len, sizeof(digit)), *qt = calloc(1, sizeof(digit));
    digit* dd_buf = calloc(buf_len, sizeof(digit));
    if (len1 < 3)
    {
    if (len1 == 1)
        tmp1 = dividend[0], dd_i -= 1;
    else if (len1 == 2)
        tmp1 = dividend[0] + 10 * dividend[1], dd_i -= 2;
    }
    else
    tmp1 = dividend[len1 - 3] + 10 * dividend[len1 - 2] + 100 * dividend[len1 - 1], dd_i -= 3;
    if (len2 == 1)
    tmp2 = divisor[0];
    else if (len2 >= 2)
    tmp2 = divisor[len2 - 2] + 10 * divisor[len2 - 1];
    if (tmp1 / tmp2 >= 10)
    tmp1 /= 10, dd_i++;
    memcpy(dd_buf, dividend + (len1 - (len2 + ((int) log10(tmp1) - 1))), len2 * sizeof(digit));
    printf("%d\n", dd_i);
    while (dd_i != -2)
    {
    memset(buf, 0, buf_len * sizeof(digit));
    qt[0] = tmp1 / tmp2;
    school_boy_multiplication(buf, qt, 1, divisor, len2);
    subtract(buf, dd_buf, buf, buf_len - ((!buf[buf_len - 1]) ? 1 : 0));
    dd_buf[0] = dividend[dd_i--];
    memcpy(dd_buf + 1, buf, len2 * sizeof(digit));
    if (buf_len < 3)
    {
        if (buf_len == 1)
        tmp1 = dd_buf[0];
        else if (buf_len == 2)
        tmp1 = dd_buf[0] + 10 * dd_buf[1];
    }
    else
        tmp1 = dd_buf[buf_len - 3] + 10 * dd_buf[buf_len - 2] + 100 * dd_buf[buf_len - 1];
    if (len2 == 1)
        tmp2 = divisor[0];
    else if (len2 >= 2)
        tmp2 = divisor[len2 - 2] + 10 * divisor[len2 - 1];
    if (tmp1 / tmp2 >= 10)
        tmp1 /= 10;
    }
    printf("\n");
}

BOOL is_greater (const digit* obj1, const digit* obj2, unsigned int len)
{
    unsigned int i;
    for (i = len - 1; (signed) i >= 0; i--)
    if (obj1[i] != obj2[i])
        return obj1[i] > obj2[i];
    return FALSE;
}

size_t digits (const digit* num)
{
    size_t i = 0;
    while (num[i] != -1)
    i++;
    return i;
}

void print (const digit* num, unsigned int len)
{
    int i = 0;
    for (i = len - 1; i >= 0; i--)
    printf("%d",num[i]);
    printf("\n");
}

    Wie gesagt, das ist nur ein Ansatz, man kann es nicht gut benutzen!
    Denk dran, daß du für die Variablen Speicher holst, und zwar mit calloc(), weil dadurch alles mit 0 vorinitialisiert wird. Wenn du malloc nimmst, musst du danach noch mit memset() alles auf 0 setzen.

    0
  • G

    Hi,
    vielen Dank, ich werde jetzt mal versuchen die Karatsuba (oder wie die heißt) und die Division zu verstehen.

    Tschau Gartnezwerg

    0
  • ?

    Den Karatsuba kannste dir anschauen, ist aber leider etwas schwierig (da 3fach rekursion), die Division bloß nicht! Das ist Schrott, der nicht funktioniert, niemand benutzt die Schuldivision für Langzahlarithmetik.

    0
  • G

    @Doktor Prokt:
    Wie siehts mit dem Vergleich aus?

    0
  • G

    Hi,
    bin gerade dabei eine Klasse dafür zu schreiben und dazu habe ich gleich zwei Fragen:

    1. kann eine string-Variable beliebig viele Zeichen aufnehmen oder nur
    256 Zeichen o.ä.

    2. kann man die Zahlen auch mit Hilfe einer Liste speichern, da sich bei den Rechenoperationen ja die Stellenzahl ändern kann und ich nicht ständig neue Felder anlegen will

    Tschau Gartenzwerg

    0
  • G

    Lass das mit dem String, und nimm ein short Array (am besten unsigned), in dem die Variable gespeichert wird. So hast du dann ein System mit einer Basis, die eine Potenz von 2 ist --> schneller.

    0
Anmelden zum Antworten