Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Lineare Kongruenzmethode (Simulationen)

Zum Testen von Software, insbesondere zur Testdatenerzeugung, zur Simulation von Ereignissen, zur Entscheidungsfindung und nicht zuletzt für die Verschlüsselung werden zuverlässige Zufallszahlen benötigt. Jedoch widerspricht sich das Konzept "Algorithmus" mit dem Konzept "Zufall".

In der Praxis hat sich dennoch ein Algorithmus zum Erstellen von sog. Pseudozufallszahlen durchgesetzt: Die lineare Kongruenzmethode.

Dazu werden drei Zahlen (a, b und m) fest vorgegeben. Eine Startzahl x0 wird als sog. seed eingetragen. Nun werden "Zufallszahlen" x1, x2, x3, … nach dem folgenden Algorithmus berechnet:

xi+1 := (a * xi + b) MODULO m

Schreiben Sie ein Programm, das vom Anwender a, b, m und x0 erfragt und danach x1 bis xm auf der Konsole ausgibt.

Diskutieren Sie die folgenden Fälle:

  • a = m
  • m = 1
  • ggT(a, b, m) > 1

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

7 Lösung(en)

import java.util.Scanner;

/**
 * Periodentests für die lineare Kongruenzmethode.
 * @author Philipp Gressly (phi@gressly.ch)
 */

public class Kongruenzmethode {

    class Random{
        long a, b, m;
        long x;
        Random(long a, long b, long m, long x0) {
            this.a = a;
            this.b = b;
            this.m = m;
            setSeed(x0);
        }
        void setSeed(long seed) {
            this.x = seed;
        }
        long nextRandom() {
            x = (a*x + b) % m;
            //System.out.println("act x:" + x);
            return x;
        }
    }
    
    public static void main(String[] args) {
        new Kongruenzmethode() . top();
    }
    
    Scanner sc = new Scanner(System.in);
    long einlesen(String msg) {
        System.out.println("Bitte " + msg + " eingeben:");
        return sc.nextLong();
    }
    
    void top() {
        long a = einlesen("A");
        long b = einlesen("B");
        long m = einlesen("M");
        long s = einlesen("seed (x0)");
        Random r = new Random(a, b, m, s);
        
        // Berechne die Periodenlänge
   
        // Periode ist max m Elemente -> erste m Elemente vorbeiziehen lassen:
        for(int i = 0; i < m; i ++) {
            r.nextRandom();
        }
        
        // Nimm die nächste Zahl (any) und zähle, wie lange es geht, bis sie wieder kommt (cnt).
        long any = r.nextRandom();
        long cnt = 1;
        while(r.nextRandom() != any) {
            cnt ++;
        }
        System.out.println("Periode: " + cnt);
    }
    
} // end of class Kongruenzmethode


                

Lösung von: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

# Zufallszahlen
def zufall(a,b,m,seed):
    x_a = seed
    for i in range(m):
        x_n =(a*x_a+b)%m
        print x_n
        x_a = x_n
        
a = long(raw_input('A: '))
b = long(raw_input('B: '))
m = long(raw_input('M: '))
s = long(raw_input('seed (x0): '))
zufall(a,b,m,s)
                

Lösung von: Martin Guggisberg (Universität Basel / PH FHNW)

/* Autor: ph. gressly */
/* Datum: 11. Dez. 2012 */
/* Lineare Kongruenzmethode. */

#include <stdio.h>

void eingabe(long * a, long * b, long * m, long * seed) {
  printf("a   : "); scanf ("%ld", a   );
  printf("b   : "); scanf ("%ld", b   );
  printf("m   : "); scanf ("%ld", m   );
  printf("seed: "); scanf ("%ld", seed);
}

long next(long old, long a, long b, long m) {
  long new;
  new = (a * old + b) % m;
  return new;
}

main() {
  long a, b, m, seed, x;
  eingabe(&a, &b, &m, &seed);
  x = seed;

  printf("Berechne alle Werte...\n");
  long i;
  long middle = m / 2 + 1;
  for(i = 0; i < middle; i++) {
    x = next(x, a, b, m);
  }
  printf("... alle Werte berechtet. Berechne Periodenlaenge...\n");
  
  long periodenlaenge = 1;
  long rep = x;
  x = next(x, a, b, m);
  while(x != rep) {
    periodenlaenge ++;
    x = next(x, a, b, m);
  }

  printf("Periode: %ld\n", periodenlaenge);
}

                

Lösung von: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

import time
t1 = time.process_time()

a = 10
b = 11
m = 1000003
x = 12
L = []
firsttime = True
periodenlaenge = 0
for i in range(1, m+1):
    x = (a * x + b) % m
    if x in L:
        if firsttime:
            periodenlaenge = i - 1
            firsttime = False
    L.append(x)
    # print(x, m)

print("Periodenlaenge", periodenlaenge)
t2 = time.process_time()
print(t2-t1, "Sekunden")        # Rechenzeit 979 Sek.

                

Lösung von: Peter Pan (Home Office)

Math.lcGen = function(a, b, mod, seed) {
  let out = [seed];
  for (let i = 1; i <= mod; i++)
    out.push( (a * out[out.length-1] + b) % mod );
  return out.slice(1);
}

console.table( Math.lcgGen( 9, 10, 11, 12) );
console.table( Math.lcgGen(11, 10, 11, 12) );
console.table( Math.lcgGen( 9, 10,  1, 12) );
console.table( Math.lcgGen( 3,  6,  9, 12) );

                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

// NET 6.x | C# 10.x | VS-2022

IEnumerable<int> GetPseudo(Params par) {
    for (int i = 0; i < par.Mod; i++)
        yield return par.Seed = (par.Seed * par.A + par.B) % par.Mod;
}

void Print(IEnumerable<int> psd)  {
    var l = string.Join(" ", psd);
    Console.WriteLine($"{new HashSet<int>(psd).Count,4} -> {l[..(l.Length > 100 ? 96 : l.Length)] + (l.Length > 100 ? " ..." : "")}");
}

new List<Params>() { 
    new ( 9, 10, 11, 12 ),
    new ( 2, 3, 11, 4 ), 
    new ( 11, 11, 1, 11 ),
    new ( 3,7, 31, 6 ), 
    new ( 4, 5, 103, 6 ), 
    new ( 101, 102, 103, 1 ) 
}.ForEach(x => Print(GetPseudo(x)));

record struct Params(int A, int B, int Mod, int Seed);
                

Lösung von: Jens Kelm (@JKooP)

// C++ 14 | VS -2022
#include <iostream>
#include <vector>
#include <unordered_set>

struct Params {
    int a, b, mod, seed;
};

const auto get_pseudo_nums(Params p) {
    std::vector<int>v{};
    for (size_t i{ 0 }; i < p.mod; ++i)
        v.push_back(p.seed = (p.seed * p.a + p.b) % p.mod);
    return v;
}

const std::ostream& print(std::ostream& os, const Params& p) {
    const std::vector<int> v{ get_pseudo_nums(p) };
    std::unordered_set<int>uos(v.begin(), v.end());
    std::cout << p.a << ", " << p.b << ", " << p.mod << ", " << p.seed << " -> " << uos.size() << "\n";
    return os;
}

int main() {
    std::vector<Params>params{ {9, 10, 11, 12}, { 2, 3, 11, 4 }, { 11, 11, 1, 11 }, { 3,7, 31, 6 }, { 4, 5, 103, 6 }, { 101, 102, 103, 1 } };
    for(const auto& p : params)
        print(std::cout, p);
}
                

Lösung von: Jens Kelm (@JKooP)

Verifikation/Checksumme:

Für a = m oder m = 1 ist eine Periode von 1 vorherbestimmt. Der ggT(a, b, m) sollte > 1 sein. Dies allein garantiert aber noch keine großen Periodenlängen. Die Periode kann nie länger als m werden.

Die folgenden Zahlen für (a, b, m und x0=seed) eingesetzt, liefern die angegebenen Periodenlängen:

a, b, m, x0 → Periodenlänge

  • 9, 10, 11, 12 → 5
  • 2, 3, 11, 4 → 10
  • 11,11,1,11 → 1
  • 3, 7, 31, 6 → 30
  • 5, 6, 31, 7 → 3
  • 101, 102, 103, 1 → 102
  • 4, 5, 103, 6 → 51
  • 2,2,1 000 003, 2 → 1 000 002
  • 10, 11, 1 000 003, 12 → 166 667
  • 11, 13, 2 000 000 011, 1 → 2 000 000 010

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 1
Schwierigkeit: Mittel
Webcode: qqrc-bps2
Autor: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen