definiowanie funkcji - square ()

definiowanie funkcji - square ()
MY
  • Rejestracja:ponad 4 lata
  • Ostatnio:ponad 4 lata
  • Postów:2
0

Mam do zrobienia program w języku c++, w którym definiujemy funkcję square(), która podnosi liczby do kwadratu. Utrudnienie jest takie, że w definiowanej funkcji nie mogę użyc operatora mnożenia.
Treść zadania jest taka:
zaimplementuj funkcję square(), nie uzywając operatora mnozenia. to znaczy operację x*x wykonaj za pomocą wielokrotnego dodawania (zacznij od zmiennej wartosci 0 i dodaj do niej
x x razy).
Zadanie to jest w ksiązce "Programowanie. Teoria i praktyka z wykorzystaniem C++." Bjarne Stroustrupa.
wszystko inne potrafię zrobić, jedynie nie wiem jak mogę zrobić funkcję podnoszącą liczbę do kwadratu nie używając mnożenia

kq
Moderator C/C++
  • Rejestracja:prawie 12 lat
  • Ostatnio:około 4 godziny
  • Lokalizacja:Szczecin
5

Przecież masz napisane.

a * b to a + a + a + ... + a, b razy.


MY
  • Rejestracja:ponad 4 lata
  • Ostatnio:ponad 4 lata
  • Postów:2
0

@kq: tak, ale jak sam napisałes: "b razy". a ja nie mogę w ogole uzywac mnozenia, czyli razy nie wchodzi w grę.
(chyba ze cos zle zrozumialam z twojej odpowiedzi, co bardzo mozliwe, jestem mocno początkująca)

AK
Materiał jest za zakresu 2 klasy podstawówki (tej dawnej stressowej szkoły, nie wiem, może teraz w ósmej?)
kq
Moderator C/C++
  • Rejestracja:prawie 12 lat
  • Ostatnio:około 4 godziny
  • Lokalizacja:Szczecin
2

Żeby wykonać jakąś akcję x razy użyj pętli.

w pseudokodzie:

Kopiuj
mult(a, b)
    result ⟵ 0
    for /b times/
        result ⟵ result + a

edytowany 1x, ostatnio: kq
PG
  • Rejestracja:ponad 6 lat
  • Ostatnio:około rok
  • Postów:10
0

Testowane. Dziala

Kopiuj
    int mySquare (int podstawa,int wykladnik)
    {
        int wynik = podstawa, licznik1 = 0;
        do
        {
            int licznik2 = 1;
            if (licznik1 > 1)
            {
                int temp = wynik;
                do
                {
                    wynik+=temp;
                    licznik2++;
                    //cout << "Potega " << licznik1 << " " << wynik << endl;
                }while(licznik2 < podstawa);
            }
            licznik1++;
        }while(licznik1 <= wykladnik);
        return wynik;
    }
edytowany 1x, ostatnio: PG
kq
square implikuje, że wykładnik to zawsze 2
PG
Dzieki, sluszna uwaga.
enedil
  • Rejestracja:prawie 12 lat
  • Ostatnio:około 21 godzin
  • Postów:1027
3

A jak nie chcesz, żeby było aż tak wolno, to można mnożenie zrealizować tak:

Kopiuj
int mult(int a, int b) {
    int result = 0;
    while (b > 0) {
        if (b & 1) {
            result += a;
        }
        a += a;
        b >>= 1;
    }
    return result;
}
edytowany 1x, ostatnio: enedil
Shalom
square then multiply zawsze na propsie :P chyba ze do RSA, to wtedy nie bo side channele
enedil
@Shalom: z całym szacunkiem, ale wersja gdzie pętla jest długości "wykładnika" to dużo poważniejszy side channel, bo bez analizy zużycia prądu masz dostęp do sporej części MSB wykładnika. No i chyba też wiesz, jak przerobić ten algorytm na nie leakujący informacji o b.
Shalom
E tam, niby co ci to daje? W przypadku RSA wiesz że wykładnik będzie miał tyle bitów co N, plus minus 1-2. Nie wiem jak to niby leakuje jakieś MSB. A co do przerabiania to wcale nie takie proste. Myślisz pewnie o square and multiply always ale to wcale nie rozwiązuje problemu, bo nadal można to sidechannelować przez doubling attack. Patrz https://hack.cert.pl/challenge/wakacje_w_spa oraz https://hack.cert.pl/challenge/kolejne_wakacje_w_spa :P
enedil
Hmm? Mówiłem o algorytmie potęgowania przez iterację wykładnik razy (porównanie do algorytmu proponowanego przez kq), w zależności od precyzji momiaru można dostać długość pętli. W przypadku RSA to daje jakieś info n.t. klucza prywatnego jeśli umiesz rozróżniać czasy obliczeń różniące się o mniej niż sqrt(N) obrotów pętli. A co do zmiany algorytmu, to racja, myślałem o square and multiply always. Przeczytam o tych atakach, dzięki za hinta

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.