How to resolve the algorithm Chinese remainder theorem step by step in the AArch64 Assembly programming language
How to resolve the algorithm Chinese remainder theorem step by step in the AArch64 Assembly programming language
Table of Contents
Problem Statement
Suppose
n
1
{\displaystyle n_{1}}
,
n
2
{\displaystyle n_{2}}
,
…
{\displaystyle \ldots }
,
n
k
{\displaystyle n_{k}}
are positive integers that are pairwise co-prime. Then, for any given sequence of integers
a
1
{\displaystyle a_{1}}
,
a
2
{\displaystyle a_{2}}
,
…
{\displaystyle \dots }
,
a
k
{\displaystyle a_{k}}
, there exists an integer
x
{\displaystyle x}
solving the following system of simultaneous congruences: Furthermore, all solutions
x
{\displaystyle x}
of this system are congruent modulo the product,
N
n
1
n
2
…
n
k
{\displaystyle N=n_{1}n_{2}\ldots n_{k}}
.
Write a program to solve a system of linear congruences by applying the Chinese Remainder Theorem. If the system of equations cannot be solved, your program must somehow indicate this. (It may throw an exception or return a special false value.) Since there are infinitely many solutions, the program should return the unique solution
s
{\displaystyle s}
where
0 ≤ s ≤
n
1
n
2
…
n
k
{\displaystyle 0\leq s\leq n_{1}n_{2}\ldots n_{k}}
.
Show the functionality of this program by printing the result such that the
n
{\displaystyle n}
's are
[ 3 , 5 , 7 ]
{\displaystyle [3,5,7]}
and the
a
{\displaystyle a}
's are
[ 2 , 3 , 2 ]
{\displaystyle [2,3,2]}
.
Algorithm: The following algorithm only applies if the
n
i
{\displaystyle n_{i}}
's are pairwise co-prime. Suppose, as above, that a solution is required for the system of congruences: Again, to begin, the product
N
n
1
n
2
…
n
k
{\displaystyle N=n_{1}n_{2}\ldots n_{k}}
is defined. Then a solution
x
{\displaystyle x}
can be found as follows: For each
i
{\displaystyle i}
, the integers
n
i
{\displaystyle n_{i}}
and
N
/
n
i
{\displaystyle N/n_{i}}
are co-prime. Using the Extended Euclidean algorithm, we can find integers
r
i
{\displaystyle r_{i}}
and
s
i
{\displaystyle s_{i}}
such that
r
i
n
i
s
i
N
/
n
i
= 1
{\displaystyle r_{i}n_{i}+s_{i}N/n_{i}=1}
. Then, one solution to the system of simultaneous congruences is: and the minimal solution,
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Chinese remainder theorem step by step in the AArch64 Assembly programming language
Source code in the aarch64 programming language
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program chineserem64.s */
/************************************/
/* Constantes */
/************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessResult: .asciz "Result = "
szCarriageReturn: .asciz "\n"
.align 2
arrayN: .quad 3,5,7
arrayA: .quad 2,3,2
.equ ARRAYSIZE, (. - arrayA)/8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main:
ldr x0,qAdrarrayN // N array address
ldr x1,qAdrarrayA // A array address
mov x2,#ARRAYSIZE // array size
bl chineseremainder
ldr x1,qAdrsZoneConv
bl conversion10 // call décimal conversion
mov x0,#3
ldr x1,qAdrszMessResult
ldr x2,qAdrsZoneConv // insert conversion in message
ldr x3,qAdrszCarriageReturn
bl displayStrings // display message
100: // standard end of the program
mov x0, #0 // return code
mov x8,EXIT
svc #0 // perform the system call
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrsZoneConv: .quad sZoneConv
qAdrszMessResult: .quad szMessResult
qAdrarrayA: .quad arrayA
qAdrarrayN: .quad arrayN
/******************************************************************/
/* compute chinese remainder */
/******************************************************************/
/* x0 contains n array address */
/* x1 contains a array address */
/* x2 contains array size */
chineseremainder:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
stp x8,x9,[sp,-16]! // save registers
mov x4,#1 // product
mov x5,#0 // sum
mov x6,#0 // indice
1:
ldr x3,[x0,x6,lsl #3] // load a value
mul x4,x3,x4 // compute product
add x6,x6,#1
cmp x6,x2
blt 1b
mov x6,#0
mov x7,x0 // save entry
mov x8,x1
mov x9,x2
2:
mov x0,x4 // product
ldr x1,[x7,x6,lsl #3] // value of n
sdiv x2,x0,x1
mov x0,x2 // p
bl inverseModulo
mul x0,x2,x0 // = product / n * invmod
ldr x3,[x8,x6,lsl #3] // value a
madd x5,x0,x3,x5 // sum = sum + (result1 * a)
add x6,x6,#1
cmp x6,x9
blt 2b
sdiv x1,x5,x4 // divide sum by produc
msub x0,x1,x4,x5 // compute remainder
100:
ldp x8,x9,[sp],16 // restaur registers
ldp x6,x7,[sp],16 // restaur registers
ldp x4,x5,[sp],16 // restaur registers
ldp x2,x3,[sp],16 // restaur registers
ldp x1,lr,[sp],16 // restaur registers
ret
/***************************************************/
/* Calcul modulo inverse */
/***************************************************/
/* x0 cont.quad number, x1 modulo */
/* x0 return result */
inverseModulo:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
mov x7,x1 // save Modulo
mov x6,x1 // A x0=B
mov x4,#1 // X
mov x5,#0 // Y
1: //
cmp x0,#0 // B = 0
beq 2f
mov x1,x0 // T = B
mov x0,x6 // A
sdiv x2,x0,x1 // A / T
msub x0,x2,x1,x0 // B and x2=Q
mov x6,x1 // A=T
mov x1,x4 // T=X
msub x4,x2,x1,x5 // X=Y-(Q*T)
mov x5,x1 // Y=T
b 1b
2:
add x7,x7,x5 // = Y + N
cmp x5,#0 // Y > 0
bge 3f
mov x0,x7
b 100f
3:
mov x0,x5
100:
ldp x6,x7,[sp],16 // restaur registers
ldp x4,x5,[sp],16 // restaur registers
ldp x2,x3,[sp],16 // restaur registers
ldp x1,lr,[sp],16 // restaur registers
ret
/***************************************************/
/* display multi strings */
/***************************************************/
/* x0 contains number strings address */
/* x1 address string1 */
/* x2 address string2 */
/* x3 address string3 */
/* other address on the stack */
/* thinck to add number other address * 4 to add to the stack */
displayStrings: // INFO: affichageStrings
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
add fp,sp,#48 // save paraméters address (6 registers saved * 8 bytes)
mov x4,x0 // save strings number
cmp x4,#0 // 0 string -> end
ble 100f
mov x0,x1 // string 1
bl affichageMess
cmp x4,#1 // number > 1
ble 100f
mov x0,x2
bl affichageMess
cmp x4,#2
ble 100f
mov x0,x3
bl affichageMess
cmp x4,#3
ble 100f
mov x3,#3
sub x2,x4,#4
1: // loop extract address string on stack
ldr x0,[fp,x2,lsl #3]
bl affichageMess
subs x2,x2,#1
bge 1b
100:
ldp x4,x5,[sp],16 // restaur registers
ldp x2,x3,[sp],16 // restaur registers
ldp x1,lr,[sp],16 // restaur registers
ret
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
You may also check:How to resolve the algorithm Arrays step by step in the lang5 programming language
You may also check:How to resolve the algorithm Find the missing permutation step by step in the Ada programming language
You may also check:How to resolve the algorithm 99 bottles of beer step by step in the Pop11 programming language
You may also check:How to resolve the algorithm Draw a cuboid step by step in the Openscad programming language
You may also check:How to resolve the algorithm Logical operations step by step in the Liberty BASIC programming language