Module 97 check digits - Decompose and Compose

Author: Josip Zohil, Koper, Slovenia , Josip.Zohil1@guest.arnes.si

 

We can calculate the remainder of a relatively small number divided by 97 using this F# function:

let mod97Small (num:int64) =

       let num97=Convert.ToDouble(num)/97.0

       Convert.ToInt64 ((num97-(Math.Truncate(num97)))*97.0)

 

But this function is unusable when the number (num) is larger then fifteen digits. In case of a large number, we can decompose it in smaller numbers (the map phase), compute the reminder modulo 97 on this small numbers and aggregate (reduce) the reminders.

In Mod97 procedure in F#  we presented the F# code for the computation of the check digits using Modulo 97. Here we present the F# code where we compute the Modulo 97 check digits in a more systematic way:

-        we decompose the large number in a list of (small) numbers ,

-        compute the reminders on the decomposed list of smaller numbers and

-        compose (aggregate) the reminders.

 

Some examples

 

The properties of modulo 97 computations are:

1) for addition: mod(x+y)=mod(mod(x)+mod(y))

2) for multiplication:  mod(x*y)=mod(mod(x)*mod(y))

 

mod(10)=10

mod(100)=mod(10*10)=3

mod(170)=mod(97) + mod(73)=mod( 0+73)=73

mod(1000)=mod(100*10)=mod(100)*mod(10)=3*10=30 

mod(100*100)=9

mod(10**8)=mod(10**4 * 10**4)= mod(9*9=81)=81

mod(10**11)=mod(1000*10**8)= mod(30*81=2430)=5

mod (10**14)=mod(10**11)*mod(10**3)=mod(5*30)=mod(150)=53

 

F# code

 

#light

namespace Modul97

module Mod97DecomposeCompose=

    open System

        //1). Modulo 97 of a "small" number, less than 16 digits long

    let mod97Small (num:int64) =

       let num97=Convert.ToDouble(num)/97.0

       Convert.ToInt64 ((num97-(Math.Truncate(num97)))*97.0)

 

    // 2). Decompose the problem - split the string of digits in chunks, for example 123 4567 8901 for chunk length 4

    let splitInChunks (chunkLen:int) (inputString:string) =

        let noChunks (inputString:string)=

           Convert.ToInt32(Math.Truncate(0.999+ (Convert.ToDouble(inputString.Length)/ Convert.ToDouble(chunkLen))))

        let diffInChunks inputString=chunkLen-(noChunks inputString)*chunkLen+inputString.Length

        let chunkLenFrom i inputString=

           match i with

            |0 -> 0

            |_ -> (diffInChunks inputString)+(i-1)*chunkLen

        let chunkLenInd i inputString=

          match i with

            |0 -> diffInChunks inputString

            |_ -> chunkLen

        let inputString00=inputString+"00"

        //  printfn "nochunks %A " (noChunks inputString00)

        List.init (noChunks inputString00) (fun i->

        //  printfn "cf %A ct %A" (chunkLenFrom i inputString00) (chunkLenInd i inputString00)

        Convert.ToInt64(inputString00.Substring(chunkLenFrom i inputString00,(chunkLenInd i inputString00)) ))

 

    //3). Calculate the modulo 97 on the decomposed list, for example mod(123)*mod(100000000) + mod(4567)*mod(10000)+mod(8901)

    let mod97List (chunkLen:int) (splitedList:int64 list)  =

       let modPowTen =

           Math.Pow(Convert.ToDouble(10),Convert.ToDouble(chunkLen))

           |>Convert.ToInt64

           |> mod97Small

           |> Convert.ToDouble 

       splitedList

       |>List.mapi (fun i (elem:int64) ->

        //printfn "%A xxxx %A xxx %A %A" elem (mod97Small elem)

        //   (Math.Pow(modPowTen,Convert.ToDouble ((splitedList.Length)- i-1 )))

        //   (Convert.ToDouble(mod97Small elem)* Math.Pow(modPowTen,Convert.ToDouble ((splitedList.Length)- i-1 )))

         Convert.ToDouble ((mod97Small elem))* Math.Pow(modPowTen, Convert.ToDouble ((splitedList.Length)- i-1 )))    

   

    //4). Compose the results - accumulate the reminders

    let accReminders (flist:float list)=

       flist

       |>List.fold_left (fun acc (ll:float)->

         //printfn "ac %A %A" ll (mod97Small(Convert.ToInt64(ll)))

         acc+ Convert.ToDouble (mod97Small(Convert.ToInt64(ll)))) 0.0 

    let tryChoiceExc chunkLen  task =

        try

           if  chunkLen<2 || chunkLen>15 then

              failwith  "Please pass a number from 2-15"

           else Choice2_1 task

        with 

          | Microsoft.FSharp.Core.Failure (ex) as  err ->   Choice2_2 err

 

    //5). Compact form of the function in one line of code

    let mod97 chunkLen inputString =

       (98L- (inputString

       |>splitInChunks chunkLen

       |>mod97List chunkLen

       |>accReminders

       |> Convert.ToInt64

       |>mod97Small)

       |>Convert.ToString).PadLeft (2,'0')

       |>tryChoiceExc chunkLen

  

    let fromChoice (res:Choice<'a,Exception>)=

       match res with

        | Choice2_1 u -> printfn "Modulo 97 check digits: %A" u; Some u

        | Choice2_2 exn -> printfn "Error: %A" exn.Message ; None

 

    //6). Example

    (mod97 14 "123456789012345678901234567890" )|>fromChoice

 

Conclusion

We calculate the check digits modulo 97 for a large number by decomposing the large number into smaller numbers and by calculating theirs modulo 97. Using the map and reduce style we reduce the list of remainders into a value that is congruent modulo 97 with the original number. We can make this calculation using a single function. The calculations of particular parts (small numbers) are independent.  

We can run in parallel the functions in 2), 3) and 4).

For extremely large numbers the value of the function accRemainders (4) can be larger then 15 digits. In that case, we can decompose the result and repeat the procedure in 1), 2), 3) and 4).