Блог

Я пытаюсь написать подпрограмму, которая принимает положительное целое число и возвращает количество шагов, необходимых для того, чтобы это целое число достигло 1, следуя гипотезе Collatz. Если входные данные равны 1, выходные данные должны быть равны нулю.

Мой псевдокод для этого, который реализует его рекурсивно (мы можем использовать только рекурсию)

 int threexplusone(int x){
    if(x == 1){
      return 0;
    }else{
      if(x % 2 == 0){
        return (threexplusone(x/2) 1);
      }else{
        return (threexplusone(3*x 1) 1);
      }
    }
}
  

Мой код выглядит так

 threexplusone:
    push rbx        ;store the rbx to stack
    mov rax, 0      ;store the base case
    cmp rdi, 1      ;compare the input with 1
    je done         ;finished the loop if equal to 1
    jmp threexplusone_recursive ;jump to the recursion

threexplusone_recursive:
    mov rbx, rdi        ;move rdi's value to rbx
    sar rbx, 1      ;divide x by 2
    sub rbx, rdi        ;substitute to get the remainder
    cmp rbx, 0      ;compare to check if the remainder is 0
    je  even        ;start the even instruction
    jne odd         ;start the odd insturction

even:
    sar rdi,1       ;divided the input by 2
    xor rax,rax
    call threexplusone  ;do the recursion

    inc rax         ;add the result by one
    jmp done        ;

odd:
    imul rdi,3      ;multiply x by 3
    add rdi, 1      ;add x by 1
    xor rax, rax
    call threexplusone  ;do the recursion
        
    inc rax     ;add the result by one
    jmp done        ;

done:
    pop rbx
    ret
  

Я тестирую его в cpp-файле, который

1. Запросите входное значение x, которое является положительным целым числом для передачи подпрограмме,

2. Запросите входное значение n, которое представляет собой количество раз для вызова подпрограммы

3. Запустите подпрограмму один раз и сохраните результат

4. Запустите подпрограмму n раз с параметром x в качестве входных данных

5. Выведите количество итераций, которое потребовалось для того, чтобы целое число сошлось к 1.

 int main(){
    int x;
    cout << "Enter a number: " << endl;
    cin >> x;
    int n; 
    cout << "Enter iterations of subroutine: " << endl;
    cin >> n;
    int result = threexplusone(x);
    for(int i = 0; i < n; i  ){
        result = threexplusone(x);
    }
    cout << result << endl;
    
    return 0;
}
  

Ожидаемый результат должен быть

 Enter a number: 
100
Enter iterations of subroutine: 
30
Steps take: 25
  

Insetead, у меня ошибка segmentaiotn

 Enter a number: 
100
Enter iterations of subroutine: 
30
Segmentation fault (core dumped)
  

Я прохожу через отладчик, вот что он мне говорит

 Program received signal SIGSEGV, Segmentation fault.
0x000000000040133a in odd ()

  

Похоже, проблема в нечетной части установки

 odd:
    imul rdi,3      ;multiply x by 3
    add rdi, 1      ;add x by 1
    xor rax, rax
    call threexplusone  ;do the recursion
        
    inc rax     ;add the result by one
    jmp done    
  

Мне интересно, какая часть моей сборки может быть причиной? Спасибо