How to resolve the algorithm Chinese remainder theorem step by step in the ARM Assembly programming language
How to resolve the algorithm Chinese remainder theorem step by step in the ARM 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 ARM Assembly programming language
Source code in the arm programming language
/* ARM assembly Raspberry PI or android with termux */
/* program chineserem.s */
/* REMARK 1 : this program use routines in a include file
see task Include a file language arm assembly
for the routine affichageMess conversion10
see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes */
/************************************/
.include "../constantes.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessResult: .asciz "Result = "
szCarriageReturn: .asciz "\n"
.align 2
arrayN: .int 3,5,7
arrayA: .int 2,3,2
.equ ARRAYSIZE, (. - arrayA)/4
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main:
ldr r0,iAdrarrayN @ N array address
ldr r1,iAdrarrayA @ A array address
mov r2,#ARRAYSIZE @ array size
bl chineseremainder
ldr r1,iAdrsZoneConv
bl conversion10 @ call décimal conversion
mov r0,#3
ldr r1,iAdrszMessResult
ldr r2,iAdrsZoneConv @ insert conversion in message
ldr r3,iAdrszCarriageReturn
bl displayStrings @ display message
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsZoneConv: .int sZoneConv
iAdrszMessResult: .int szMessResult
iAdrarrayA: .int arrayA
iAdrarrayN: .int arrayN
/******************************************************************/
/* compute chinese remainder */
/******************************************************************/
/* r0 contains n array address */
/* r1 contains a array address */
/* r2 contains array size */
chineseremainder:
push {r1-r9,lr} @ save registers
mov r4,#1 @ product
mov r5,#0 @ sum
mov r6,#0 @ indice
1:
ldr r3,[r0,r6,lsl #2] @ load a value
mul r4,r3,r4 @ compute product
add r6,#1
cmp r6,r2
blt 1b
mov r6,#0
mov r7,r0 @ save entry
mov r8,r1
mov r9,r2
2:
mov r0,r4 @ product
ldr r1,[r7,r6,lsl #2] @ value of n
bl division
mov r0,r2 @ p
bl inverseModulo
mul r0,r2,r0 @ = product / n * invmod
ldr r3,[r8,r6,lsl #2] @ value a
mla r5,r0,r3,r5 @ sum = sum + (result1 * a)
add r6,#1
cmp r6,r9
blt 2b
mov r0,r5 @ sum
mov r1,r4 @ product
bl division
mov r0,r3
100:
pop {r1-r9,pc} @ restaur registers
/***************************************************/
/* Calcul modulo inverse */
/***************************************************/
/* r0 containt number, r1 modulo */
/* x0 return result */
inverseModulo:
push {r1-r7,lr} @ save registers
mov r7,r1 // save Modulo
mov r6,r1 // A r0=B
mov r4,#1 // X
mov r5,#0 // Y
1: //
cmp r0,#0 // B = 0
beq 2f
mov r1,r0 // T = B
mov r0,r6 // A
bl division // A / T
mov r0,r3 // B and r2=Q
mov r6,r1 // A=T
mov r1,r4 // T=X
mls r4,r2,r1,r5 // X=Y-(Q*T)
mov r5,r1 // Y=T
b 1b
2:
add r7,r7,r5 // = Y + N
cmp r5,#0 // Y > 0
bge 3f
mov r0,r7
b 100f
3:
mov r0,r5
100:
pop {r1-r7,pc}
/***************************************************/
/* display multi strings */
/***************************************************/
/* r0 contains number strings address */
/* r1 address string1 */
/* r2 address string2 */
/* r3 address string3 */
/* other address on the stack */
/* thinck to add number other address * 4 to add to the stack */
displayStrings: @ INFO: affichageStrings
push {r1-r4,fp,lr} @ save des registres
add fp,sp,#24 @ save paraméters address (6 registers saved * 4 bytes)
mov r4,r0 @ save strings number
cmp r4,#0 @ 0 string -> end
ble 100f
mov r0,r1 @ string 1
bl affichageMess
cmp r4,#1 @ number > 1
ble 100f
mov r0,r2
bl affichageMess
cmp r4,#2
ble 100f
mov r0,r3
bl affichageMess
cmp r4,#3
ble 100f
mov r3,#3
sub r2,r4,#4
1: @ loop extract address string on stack
ldr r0,[fp,r2,lsl #2]
bl affichageMess
subs r2,#1
bge 1b
100:
pop {r1-r4,fp,pc}
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../affichage.inc"
You may also check:How to resolve the algorithm Catmull–Clark subdivision surface step by step in the OCaml programming language
You may also check:How to resolve the algorithm URL decoding step by step in the Raku programming language
You may also check:How to resolve the algorithm Symmetric difference step by step in the Pike programming language
You may also check:How to resolve the algorithm Set step by step in the Factor programming language
You may also check:How to resolve the algorithm Chaos game step by step in the zkl programming language