Dotaz: Java - metoda opak. ctvercu

[ahad!3l]

Zdravim. Dostal jsem za ukol napsal program v Jave, ktery ma umocnit cele zadane cislo. V Jave nemam zadne zkusenosti, takze si ani s takovou trivialni veci bohuzel nevim rady. Chtel bych nekoho proprosit, kdyby by me mohl postrcit. Cele zadani zni takto:

Napište funkci, která umocní zadané celé číslo a (typu long) na b (typu long) ve zbytkové třídě Zn; vše jen pomocí násobení. Vstupem funkce jsou hodnoty a,b,n; výstupem je a^b (a na b; POZOR v jave je to XOR) v Zn (opět typu long). K umocnění použijte metodu opakovaných čtverců. Funkci použijte v programu, který z klávesnice načte hodnoty a, b (b>=0), n (n>1); vypočte a^b (umocní a na b) v Zn a výsledek vypíše.

Počítání ve zbytkové třídě Zn (modulo n) je takové, že na výsldek aplikujete modulo n (tj: a+b v Zn = (a+b)%n; a*b v Zn = (a*b)%n atd.)

A nasledne vysvetlivky:
1. Inicializujeme pomocnou proměnnou x=1.
2. Mocnitel (b) se zapíše v binárním kódu (např. 11 dekadicky se zapíše binárně jako 1011); mezi znaky binárního kódu vepíšeme znak s (s jako square; např. pro 11 dekadicky, tedy 1011 binárně, je to 1s0s1s1).,
3. Tuto posloupnost procházíme zleva doprava, pokud narazíme na 1, vynásobíme x hodnotou a; pokud narazíme na 0 neděláme nic; pokud narazíme na s umocníme x na druhou (uděláme čtverec). Všechny zmíněné operace jsou modulo n (tedy %n). Poté, co projdeme celý řetězec, je v proměnné x uložen výsledek.

* Řetězec (např. 1s0s1s1) nemusíme vytvářet, je jen pro představu. NEPŘIJÍMÁM úkoly s použitím řetězců. Metodu implementujeme pomocí cyklu, jehož tělo se bude opakovat maximálně tolikrát, kolik je bitů v příslušném datovém typu.
Postupuji zatim dobre?

package dcv4;

public class Zn {

	
	public static void main(String[] args) {
		java.util.Scanner jc = new java.util.Scanner(System.in);
		
		System.out.printf("Zadejte n: ");
		
		
		long a, b = 1011;
	int n;
	int x = 1;
	
	if (a^b) {
    if (b>=0, n>1) {
	}

Dekuji za kazdou radu.

Odpovědi

[Messa]

Myslím, že nepostupuješ. Jestli zkoušíš to 1011 z příkladu, tak to je jen binárně zapsané číslo 11 (jedenáct), nikoli tisíc jedenáct. Také se mi nezdá a^b, proč to tam je? Asi bys měl procházet číslo b po jednotlivých bitech a podle hodnoty daného bitu pracovat s číslem x.

[moira]

Zkus sem hodit něco, co bude přeložitelné... v prvním if není výsledkem boolean, n nemáš inicializované, co znamená ta čárka v druhém if?

[x22]

Ono to nie je az tak trivialne. nasobenie mod long sa pocita blbo kvoli moznemu preteceniu. Cudujem sa, ze o tomto problem sa v zadani nepise, ked uz je tam celkom podrobny postup.

Zistit, aky je k-ty bit cisla b sa da zistit 2 operatormi (vysledok je rovno boolean).

[Marek]

>pomocí cyklu, jehož tělo se bude opakovat maximálně tolikrát, >kolik je bitů v příslušném datovém typu Zdravim.

Mame (b)_10 = (b_p b_(p-1) ... b_1 b_0)_2

Skus sa zamysliet ako zo znalosti: (v dalsom (...) znamena v dvojkovej sustave)

a^(b_p ... b_1) mod n mozno vypocitat

1. a^(b_p ... b_1 0) mod n
2. b) a^(b_p ... b_1 1) mod n

Je to vlastne popisane v hinte 3.

Cyklus, ktory zbehne maximalne tolkokrat, kolko je bitov v reprezentacii datoveho typu pre b sluzi zase na to, aby sa dala zistit reprezentacia b v dvojkovej sustave zlava. (Vacsinou sa ide sprava, t.j. od poslednej cislice.)

Tieto dve veci treba dat dokopy a mas program.

Priklad:

a^6 mod n, predpokladame, ze datovy typ reprezentujuci 6 ma 4 
bity. Preto, 6 je reprezentovane ako 0101.

Na zaciatku mame a^(0) mod n = 1.

Zistime prvu cislicu 4-bitovej reprezentacie cisla 6:

0: -> pouzijeme postup, ako z a^(0) mod n -> a^(00) mod n

V dalsom kroku zistime 2. cislicu:

1: -> pouzijeme postup, ako z a^(00) mod n -> a^(001) mod n

3. cislica:

0: a^(001) mod n -> a^(0010) mod n

4. cislica:

1: a^(0010) mod n -> a^(00101) mod n

a mame vysledok. 

Snad to aspon trochu pomoze.

Marek

[ahad!3l]

Moc dekuju za rady, ale je to na me stejne slozite. Javu jsem pred 2 tydny videl poprve. Jinak tady jde videt zadani asi lepe..

[vaki]

Algoritmus je to pěkný, na pár řádků. Jeho obtížnost je pro začátečníky řekl bych střední.

Popis algoritmu v odkazovaném dokumentu je dostatečný. Dle zkušeností se však začátečník při pohledu na tento popis vyděsí a začne přemýšlet víc o tom co neví než o tom co ví.

algoritmus jsem si naprogramoval a i když nemám moc čas ho testovat zdá se být funkční. Nejprve se úplně vykašlete na načítání hodnot a zaměřte se na samotný výpočet tak, jak je popsaný v zadání.

Krok 1) Inicializovat proměnnou - tak to je snad jasné

Krok 2) Převést na binární číslo v textovém řetězci je zadavatelem zakázané, proto jediné co potřebujeme od toho kroku je zjistit kolik bitů vlastně dané čáslo zaujímá. Alternativou je použít konstantu Long.BITS ale v tom případě by se vždy testovali všechny bity. Nevím zda je zadavatelme přijatelné řešení kupříkladu níže popsaný převod. Nechám na Vašem uvážení

int pocetBitu=Long.toBinaryString(b).length()

Krok 3) Zde je třeba se zamyslet. Zadavatel výslovně zakázal používat řetězec. Přesto jsme schopni zjistit zda je na požadovaném místě binární reprezentace čísla b jednička nebo nula. Pro i-tý bit čísla si jednoduchým výpočtem 2 na i-tou vytvořte bitovou masku a jejich ANDem (operace & ) zjistíte zda je tam jednička nebo ne.

2a) je jednička? Pak podle popisu provede násobení x číslem a (avšak v modulu zn) tedy

x = (x*a)%zn;

2b) je nula? neděláme nic

2c) ještě musíme ošetřit stav 's', a při rychlém pohledu do řetězce v příkladu je jasné, že znak 's' následuje za každým znakem, kromě posledního. Tedy pokud pracujeme s jiným než posledním znakem, provedeme navíc krok x na druhou opět v modulu zn

x = (x*x)%zn;

Když takto projdeme všechny bity čísla b, máme v x uložený výsledek.

--- Algoritmus Vám samozřejmě mohu poslat, ale samotné řešení bez jeho pochopení Vám v dlouhodobém výhledu stejně nepomůže.

[ahad!3l]

Pokud byste byl tak hodny, reseni by se mi hodilo. ( ahadiel@centrum.cz )
Alespon bych si to okoukal, ikdyz mi ve studiu nepomuze, to mate pravdu. ( ) Ja totiz moc nechapu celkove zadani. Umocneni se mi podarilo provest takto:

public class Mocnina {
    
    public static void main(String[] args) {
        java.util.Scanner in = new java.util.Scanner(System.in).useLocale(java.util.Locale.US);
        
        for (; ; ) {
            System.out.println("Zadej dvě celá čísla: ");
            int m = in.nextInt();
            int n = in.nextInt();
            int mocnina = 1;
            int nn = n;
            int mm = m;
            while (nn > 0) {
                if (nn % 2 == 1) {
                    mocnina = mocnina * mm;
                }
                mm = mm * mm;
                nn = nn / 2;
            }
            System.out.println(m + " na " + n + " = " + mocnina);
        }
    }
}

Ovsem nevim si rady s temi bity, zbytkovou tridou Zn. Celkove se mi zda, ze je to celkem neumerne nasim schopnostem, jelikoz 90% tridy v Jave pred 2 tydny teprve zacalo, vcetne me. Mam ale vybornou knizku, tak se snad moje schopnosti brzy rozsiri. Moc Vám děkuji za ochotu.

[vaki]

Moje metoda pro mocinu:

public static long MetodaOpakovanychCtvercu(long a, long b, long zn){
		// zjistíme počet bytů mocnitele (parametr b)
		int pocetBitu = Long.toBinaryString(b).length();

		// inicializace výsledkové proměnné
		long x = 1;
		
		// procházení čísla
		for(int i=pocetBitu-1; i>=0; i--){			
			// Spočítáme bitovou masku pro i-tý bit
			long mask = Math.round(Math.pow(2, i));
			
			/* je-li i-tý bit čísla b 1 provedeme operaci pro znak '1'*/
			if((b & mask) == mask )
				x = (x*a)%zn;

			/* pokud se nejedná o poslední bit, provedem operaci znak 's' */
			if(i > 0)
				x = (x*x) % zn;
		}
		
		return x;
	}

[ahad!3l]

Uff..no budu to muset prostudovat a nejak se s tim poprat. Tohle bych teda nezplodil. Dekuji, ze jste tam vlozil i komentare. Alespon vim, co jaky radek ma za ukol delat.

[moira]

Lepší než
long mask = Math.round(Math.pow(2, i));
je
long mask = 1l << i;

[Radovan]

Hele, nejste z jedné třídy? http://forum.root.cz/index.php?topic=1056.0

[Saljack]

Ha ha nejsi náhodou z FELu a tohle máš do algoritmizace tohle jsme také dělali.