3. große Zahlen

große Zahlen

  • G

    Dividieren ist auch nicht so schwer. Es ist schwer, dass es schnell wird. Aber mit meiner "bitweisen Approximation" hab ichs ganz gut hinbekommen, glaub ich.

    0
  • R

    ich würde einfach GNU MP benutzen 🙂

    http://www.swox.com/gmp/

    0
  • G

    Hi @ all,
    ich möchte das so ein bisschen als Übung nutzen. Außerdem interessiert mich
    wie manche Leute Primzahlen von mehreren Seiten ausrechnen.

    @ Devil667: 100 war nur ein Bsp. (hatte keine Lust die Null meiner Tastatur zu quälen).

    @ Mr. N: wie kann ich denn die Basis 2^32 darstellen? long kann IMHO doch nur Speicher für 10^8 reservieren, oder?

    @ kingruedi: ich interessiere mich für das Prinzip und würde es deshalb gerne selber machen (wird zwar lange nicht so gut wie die GNU MP)

    Tschau Gartenzwerg

    0
  • ?

    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