Home > Uncategorized > The 3n+1 problem–the hard way

The 3n+1 problem–the hard way

A sample problem from the book Programming challenges is published here and it has been named The 3n+1 problem. It does not take a great effort to come up with a solution; in F# it might look like:

let threeNPlusOne = Seq.unfold (fun n -> let n’ = if n%2=0 then n/2 else n*3+1 in Some(n,n’))

 

let cycleLength n = 1 + n |> threeNPlusOne |> Seq.takeWhile ((<>) 1) |> Seq.length

 

let solve i j = seq { i..j } |> Seq.map cycleLength |> Seq.max

 

Or maybe, using a more imperative style, it might look like:

let solve i j =

    let mutable maxLen = 0

    for n in i..j do

        let mutable n’ = n

        let mutable c = 1

        while n’ <> 1 do

            n’ <- if n’%2=0 then n’/2 else n’*3+1

            c <- c + 1

        if c > maxLen then

            maxLen <- c

    maxLen

 

Ok, that was fun for a little while but not a real challenge. Rewriting the solution in assembler makes it more interesting:

int solve(int i, int j)

{

    __asm

    {

        xor    eax, eax    ; maxLen = 0

        mov ecx, i      ; for n = i..j

repeat_for:       

        cmp ecx, j

        jg    done       

        push eax

        mov ebx, 1        ; c = 1

        mov edx, ecx    ; np = n

repeat_while:       

        cmp edx, 1

        je  term_loop   ; while (np <> 1)

        inc    ebx            ; c++

        mov eax, edx

        shr eax, 1

        jnc case_even

        mov eax, edx    ; np = np * 3 + 1

        shl edx, 1

        add edx, eax

        inc edx

        jmp repeat_while

case_even:

        mov edx, eax    ; np = np / 2

        jmp repeat_while

term_loop:

        pop    eax

        inc ecx            ; [n++]

        cmp    ebx, eax     ; if c > maxlen

        jle repeat_for

        mov eax, ebx    ; c = maxlen

        jmp repeat_for

done:

    }

}

 

Erhmm. That’s all for today. Good night. Smile

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: