Неправильно подсчитывается период генератора случайных чисел в основе которого лежит линейный конгруэтный метод, что делать?

Question

   public class Main {
    
        public static void main(String[] args) {
            double x = 1;
            int count = 0;
            int per = 0;
            double num = 0;
            int m = (int) Math.pow(2, 32);
            double M = Math.pow(2, 32);
            int b = 134775813;
            int k = 1;
            ArrayList<Double> array = new ArrayList<>();
            for (int j = 0; j < m; j++) {
    
                x = (k * x + b) % M;
                num = x / M;
    
                array.add(num);
                //Нахождение периода генератора
                count = Collections.frequency(array, num);
                if (count >= 2) {
                    per = j;
                    break;
                }
            }
            System.out.println(per);
        }
    }

Answer 1

Считает неправильно потому что неправильно реализован сам метод.

Вы делаете

x = (k * x + b) % M;

М заведомо очень большое что будет вам гарантировать большой остаток.
М почему вещественное
Зачем x делить на М. М большое х меньше результат num вещественное меньше 1.
Collections.frequency вернет количество num в списке а не период.

Исправьте по замечаниям и можно будет подумать.

Updated.

Чуток поменял ваш код.

public static void main(String[] args) {
    double x = 1;
    int count = 0;
    int per = 0;
    double num = 0.0;
    long m = Math.round(Math.pow(2, 32));
    double M = 100000.0; // Math.pow(2, 32);

    long b = 134775813L;
    long k = 1L;

    List<Double> array = new ArrayList<>();
    for (int j = 0; j < m; j++) {

      x = (k * x + b) % M;
      num = x / M;

      if (array.contains(num)) {
        count = array.indexOf(num);
        per = j - count;
        break;
      }
      array.add(num);
    }
    System.out.println(String.format("period = %d", per));
    // System.out.println(array);
  }
}

Ваши ошибки.

int m = (int) Math.pow(2, 32); m = 0 в результате
double M = Math.pow(2, 32); если брать такое же число то вы получите период М
count = Collections.frequency(array, num); - возращяет количество num в массиве

и для примера из вики

public static void main(String[] args) {
    double x = 7;
    int count = 0;
    int per = 0;
    double num = 0.0;
    long m = Math.round(Math.pow(2, 32));
    double M = 10.0; // Math.pow(2, 32);

    long b = 7L;
    long k = 7L;

    List<Double> array = new ArrayList<>();
    for (int j = 0; j < m; j++) {

      x = (k * x + b) % M;
      num = x / M;

      if (array.contains(num)) {
        count = array.indexOf(num);
        per = j - count;
        break;
      }
      array.add(num);
    }
    System.out.println(String.format("period = %d", per));
    // System.out.println(array);
  }
}

периоды совпадают

Update 2. для примера в коментариях. Использовал более быструю структуру в данном случае.

public static void main(String[] args) {
    double x = 7;
    int count = 0;
    int per = 0;
    double num = 0.0;
    long m = Math.round(Math.pow(2, 32));
    double M = 1771875.0; // Math.pow(2, 32);

    long b = 374441L;
    long k = 2416L;

    Map<Double, Double> array = new HashMap<>();
    for (int j = 0; j < m; j++) {

      x = (k * x + b) % M;
      num = x / M;

      if (array.containsKey(num)) {
        // count = array.indexOf(num);
        // per = j - count;
        per = array.size();
        break;
      }
      array.put(num, num);
    }
    System.out.println(String.format("period = %d", per));
    // System.out.println(array);
  }

БЛОГ НА HUSL

Неправильно подсчитывается период генератора случайных чисел в основе которого лежит линейный конгруэтный метод, что делать?

Ответы (1 шт):