Mnożenie I Dzielenie

[DragonFly]

Witam

 

Mam taki problem od 2 tygodni proboje wymyślić jakiś sensowny algorymt który zapewniłby mi mnożenie i dzielenie liczb. Nie chodzi tu o mnożenie i dzielenie małych liczb ale takich co to mają po 200 lub 300 cyfr...

Bardzo porosze o pomoc

 

Pozdrawiam

Edytowane 22 Czerwca 2005 przez DragonFly

[NetWalker]

Mnożenie polecam dokładnie tak jak to się robi na kartce [ mnożenie pisemne ].

Dzielenie jest troche bardziej skomplikowane. Używamy dodawania liczby przez którą dzielimy z dodanymi do niej na końcu zerami. Dodajemy w pętli do zmiennej początkowo zerowej aż ta zmienna nie będzie większa niż liczba dzielona. Zapisujemy wynik i odejmujemy zero od liczby dzielonej. Tak w kółko. Jestem pewien ze wydaje to się trudne do skumania. [ szczególnie z mojego objaśnienia ].

 

Poszukaj w necie o dzieleniu liczb dwójkowych [ są strony z wyjaśnieniami ]. Na ich podstawie zrobisz to samo w kodzie dziesiętnym itp.

 

Jeżeli chcesz to moge przysłać mój kod w C++, którym rozwiązywałem zdanie ze Staszica: http://ki.staszic.waw.pl/task.php?name=rachunki. Niestety kod jest troche zawiły ze względów optymalizacyjnych [ nie łatwo było zdobyć 100 punktów :P ]

[ayem]

poszukaj klasy do C 'BigInt' czy jakos tak - tam jest to zrobione - tylko sienie przeraz :D

[rojmarek]

jaki język??

[Ragnor]

Co do mnożenia mozna zastosować algorytm chłopów rosyjskich lub za pomocą metody dziel i zwycięzaj podzielić mnożone liczy na 2 częsci i wtedy wykonać 3 operacje mnożenia na liczbach o połowe krótszych.

[~blacksheep]

Metoda którą podaje Ragnor jest optymalniejsza od mnożenia "pisemnie" ale jest tym wydajniejsza im mniejszy system liczbowy (czyli w systemie dwójkowym różnice są największe). Najwydajnie było by właśnie tak - plus operując na bitach.

[Contrast]

Panowie a dzieląc także można zastosować metodę dziel i zwycięzaj

[bosoro]

Mnożenie polecam dokładnie tak jak to się robi na kartce [ mnożenie pisemne ].

Dzielenie jest troche bardziej skomplikowane. Używamy dodawania liczby przez którą dzielimy z dodanymi do niej na końcu zerami. Dodajemy w pętli do zmiennej początkowo zerowej aż ta zmienna nie będzie większa niż liczba dzielona. Zapisujemy wynik i odejmujemy zero od liczby dzielonej. Tak w kółko. Jestem pewien ze wydaje to się trudne do skumania. [ szczególnie z mojego objaśnienia ].

 

Witam :-)

 

Czy moglbys mi pomoc? jak otrzymac reszte z dzielenia:

106000347270121212121210252100 mod 97

Sadze, ze mozna do tego uzyc Twojego programu...

Czy bylbys tak uprzejmy i podrzucil mi zrodlo?

 

pozdrawiam :-)

[Polar]

Wrzuce tu implementacje Klasy BigInteger co prawda jest w C# ale jest godna uwagi.

Niestety kodu nie wrzuce bo post może mieć tyko 32 kb a ta klasa ma 108 kb ;D

 

W każdym razie wynik jaki podała dla twojej liczby to 18

link do kodu... ( coś nie działa chyba , wyrażenie regularne dla tego linka bo nie chce go przemienić na url )

 

www.badongo.com/file.php?file=BigInteger class__2005-12-30_BigInteger.cs

 

public static class Tester{	public static void Main(string[] args)	{		BigInteger a = new BigInteger("106000347270121212121210252100", 10);		Console.WriteLine("{0} mod 97 = {1}", a, a % 97);		/// na ekranie pokaże sie:		/// 106000347270121212121210252100 mod 97 = 18	}}

Edytowane 30 Grudnia 2005 przez razor1

[bosoro]

dzieki za pomoc :-)

 

Pisze to w php, a rozwiazalem to w ten sposob (dzieki pomocy NetWalkera ;-))

 

<?php
$nr = "106000347270121212121210252100";
$liczba = "97";

function reszta($nr, $liczba) {

[indent]$A = $nr;
$B = $liczba;
$A_prim = substr($A, 0, strlen($B));

for( $i=strlen($B); $i<=strlen($A); $i++ )
{
[indent]while($A_prim > $B) { $A_prim -= $B;	}
$A_prim .= substr($A, $i, 1);[/indent]
}

return $A_prim;
}

echo reszta($nr, $liczba);
[/indent]
?>

 

Moze komus sie przyda ;-)

Edytowane 31 Grudnia 2005 przez bosoro