The first 1000 primes:
uses console
============
class Primes
============
'
int nn 'array elements
sys p 'array buffer address
'
method constructor(int n)
=========================
'generate primes
int i,j,k,t
t=n
redim quad q(t+1)
quad r
quad m=1
indexbase 0
nn=n
i=0
while i<t
k=1
for j=2 to i-1
r=mod(m,q[j])
if r=0
k=0
exit for
endif
next
if k
i++
q[i]=m
endif
m++
wend
nn=n
p=@q
end method
'
method get(int i) as quad
if i<1 or i>nn
exit method
endif
quad q at (i*8+p)
return q
end method
'
end class 'Primes
'
'TEST
=====
new Primes P(1000)
int i
for i=1 to P.nn
print i tab P.get(i) cr
next
del P
wait
Blum Primes are primes with modulus 4 = 3. That means: (PrimeNum and 3)=3.
uses console
================
class BlumPrimes
================
'
int nn 'array elements
sys p 'array buffer address
'
method constructor(int n)
=========================
'generate primes
int i,j,k,t
t=n*2
redim quad q(t+1)
quad r
quad m=1
indexbase 0
nn=n
i=0
while i<t
k=1
for j=2 to i-1
r=mod(m,q[j])
if r=0
k=0
exit for
endif
next
if k
i++
q[i]=m
endif
m++
wend
'filter for Blum primes
j=0
for i=1 to t
k=q[i] 'clipped to 32bits
if (k and 3) = 3 'quick modulo 4
j++
q[j]=q[i]
if j>=nn
exit for
endif
endif
next
nn=j
'print i cr
p=@q
end method
'
method get(int i) as quad
if i<1 or i>nn
exit method
endif
quad q at (i*8+p)
return q
end method
'
end class 'BlumPrimes
'
'TEST
=====
new BlumPrimes BP(1000)
int i
for i=1 to BP.nn
print i tab BP.get(i) cr
next
del BP
wait
With some assistance from Bing Copilot:
'BlumBlumShub Randomizer
uses console
================
class BlumPrimes
================
'
int nn 'array elements
sys p 'array buffer address
'
method constructor(int n)
=========================
'generate primes
int i,j,k,t
t=n*2
redim quad q(t+1)
quad r
quad m=1
indexbase 0
nn=n
i=0
while i<t
k=1
for j=2 to i-1
r=mod(m,q[j])
if r=0
k=0
exit for
endif
next
if k
i++
q[i]=m
endif
m++
wend
'filter for Blum primes
j=0
for i=1 to t
k=q[i] 'clipped to 32bits
if (k and 3) = 3 'quick modulo 4
j++
q[j]=q[i]
if j>=nn
exit for
endif
endif
next
nn=j
print i cr
p=@q
end method
'
method get(int i) as quad
if i<1 or i>nn
exit method
endif
quad q at (i*8+p)
return q
end method
'
end class 'BlumPrimes
'
'TEST
'new BlumPrimes BP(1000)
'int i
'for i=1 to BP.nn
' print i tab BP.get(i) cr
'next
'del BP
'wait
==================
class BlumBlumShub
==================
'
quad P,Q,N,state
'
method constructor(dword iP, iQ, iseed)
'P(P), Q(Q), N(P * Q), state(seed) {}
P=iP
Q=iQ
N=iP*iQ
state=iseed
end method
method get() as quad
'state = mod(state * state,N)
state = (state * state) mod N
return state
end method
method getBit() as int
return mod(get(), 2)
end method
end class 'BlumBlumShub
'TEST
=====
' Choose large Blum prime numbers P and Q
' Blum prime numbers (where P ≡ 3 (mod 4))
quad P = 17159 '11
quad Q = 17167 '23
quad seed = 1234
new BlumBlumShub brnd(P, Q, seed)
'
' Generate a sequence of random numbers
int i
for i=0 to 19
print i tab " " brnd.get() cr
next
'
wait
del brnd
The given code consists of two classes: `BlumPrimes` and `BlumBlumShub`. The `BlumPrimes` class generates Blum primes and stores them in an array. The `BlumBlumShub` class is a pseudorandom number generator that uses two large Blum prime numbers P and Q to generate a sequence of random numbers.
Here's an optimized version of the code in x86 ASM using the System V AMD64 ABI:
```assembly
section .data
; Test data
P dq 17159
Q dq 17167
seed dq 1234
fmt db "%d: %lu", 10, 0
section .bss
; BlumBlumShub object
state resq 1
N resq 1
section .text
global main
extern printf
; Function to check if a number is a Blum prime (returns 1 if true, 0 otherwise)
; Input: RDI (number to check)
; Output: RAX (1 if Blum prime, 0 otherwise)
is_blum_prime:
push rbp
mov rbp, rsp
; Check if the number is prime
; ... (Implement a prime checking algorithm like Miller-Rabin or trial division)
; Check if the number is congruent to 3 modulo 4
mov rax, rdi
and rax, 3
cmp rax, 3
jne .not_blum_prime
mov rax, 1 ; The number is a Blum prime
jmp .end
.not_blum_prime:
xor rax, rax ; The number is not a Blum prime
.end:
leave
ret
; BlumBlumShub constructor
; Input: RDI (P), RSI (Q), RDX (seed)
; Output: None
blum_blum_shub_constructor:
push rbp
mov rbp, rsp
mov rax, [rdi] ; Load P
imul rsi ; Multiply by Q
mov [N], rax ; Store N
mov rax, [rdx] ; Load seed
mov [state], rax ; Store state
leave
ret
; BlumBlumShub get method
; Input: None
; Output: RAX (random number)
blum_blum_shub_get:
push rbp
mov rbp, rsp
mov rax, [state] ; Load state
imul rax ; Square state
mov rdx, 0 ; Clear RDX for division
div qword [N] ; Divide by N (remainder in RDX)
mov [state], rdx ; Store new state
mov rax, rdx ; Return the remainder as the random number
leave
ret
; BlumBlumShub getBit method
; Input: None
; Output: RAX (0 or 1)
blum_blum_shub_get_bit:
push rbp
mov rbp, rsp
call blum_blum_shub_get ; Get random number
and rax, 1 ; Get least significant bit
leave
ret
main:
; Initialize BlumBlumShub
mov rdi, [P]
mov rsi, [Q]
lea rdx, [seed]
call blum_blum_shub_constructor
; Generate a sequence of random numbers
xor ecx, ecx ; Counter
.loop:
cmp ecx, 20
jge .end_loop
; Print the index and random number
mov rdi, fmt
mov rsi, ecx
call blum_blum_shub_get
mov rdx, rax
xor rax, rax
call printf
inc ecx
jmp .loop
.end_loop:
; Exit
xor eax, eax
ret
```
This x86 ASM code attempts to optimize the given code by using efficient arithmetic operations and following the System V AMD64 ABI for function calls. It uses the `is_blum_prime` function to check if a number is a Blum prime, which can be implemented using a prime checking algorithm like Miller-Rabin or trial division. The `blum_blum_shub_constructor`, `blum_blum_shub_get`, and `blum_blum_shub_get_bit` functions implement the BlumBlumShub pseudorandom number generator.
Using MiSTRAL AI (https://chat.mistral.ai/chat/)
Here a second shot:
Here's a simple implementation of a trial division prime checking algorithm in x86 ASM:
```assembly
; Function to check if a number is prime using trial division
; Input: RDI (number to check)
; Output: RAX (1 if prime, 0 otherwise)
is_prime:
push rbp
mov rbp, rsp
cmp rdi, 2 ; Check if the number is less than 2
jl .not_prime
cmp rdi, 3 ; Check if the number is 3
je .prime
mov rax, rdi
and rax, 1 ; Check if the number is even
jz .not_prime
mov rax, 3 ; Start checking divisibility from 3
.check_divisibility:
cmp rax, rdi
jge .prime ; If we've reached the number itself, it's prime
mov rdx, 0
div rax ; Divide the number by the current divisor
cmp rdx, 0 ; Check if there's a remainder
jz .not_prime ; If there's no remainder, the number is not prime
add rax, 2 ; Increment the divisor by 2 (only check odd divisors)
jmp .check_divisibility
.prime:
mov rax, 1 ; The number is prime
jmp .end
.not_prime:
xor rax, rax ; The number is not prime
.end:
leave
ret
```
This function checks if a number is prime by trying to divide it by all odd numbers up to its square root (since a larger factor of the number would have already been tried as a smaller factor of another number). If none of the divisors divide the number evenly, then the number is prime.
To use this prime checking algorithm in the `is_blum_prime` function, replace the comment `; Check if the number is prime` with a call to `is_prime`:
```assembly
; Function to check if a number is a Blum prime (returns 1 if true, 0 otherwise)
; Input: RDI (number to check)
; Output: RAX (1 if Blum prime, 0 otherwise)
is_blum_prime:
push rbp
mov rbp, rsp
; Check if the number is prime
call is_prime
cmp rax, 0
je .not_blum_prime
; Check if the number is congruent to 3 modulo 4
mov rax, rdi
and rax, 3
cmp rax, 3
jne .not_blum_prime
mov rax, 1 ; The number is a Blum prime
jmp .end
.not_blum_prime:
xor rax, rax ; The number is not a Blum prime
.end:
leave
ret
```
Definitely worth optimizing these algorithms, but the problem inherent in BlumBlumShub is the requirement for division to calculate the modulus. Division is always computationally expensive, requiring hardware iteration. So BlumBlumShub would not be the best choice for high-speed use, for instance generating large texture maps.