Back
Close

BrainFuck part 4 - Advanced maths

DPAmar
2,430 views
Previous: Integer square root - part 1, Newton's method

Square root, part 2 : Naive but efficient method

In the previous post, we implemented an efficient (or generally efficient) way to compute integer square root.

However, even if there are only a few steps, all the divisions, sums, ... take a lot of time while executed in BF. So, few iterations, but expensive ones...

A very naive approach would be to check 1, 2, 3, ... : is the current value still less than sqrt(n), or more precisely x^2 <= n ?

And this can be achieved very efficiently in BF, by subtracting odd numbers : example with 42

  • test 0: 42 - 1 = 41 ( = 42 - 1^2), positive
  • test 1: 41 - 3 = 38 ( = 42 - 2^2), positive
  • test 2: 38 - 5 = 33 ( = 42 - 3^2), positive
  • test 3: 33 - 7 = 26 ( = 42 - 4^2), positive
  • test 4: 26 - 9 = 17 ( = 42 - 5^2), positive
  • test 5: 17 - 11 = 6 ( = 42 - 6^2), positive
  • test 6: 6 - 13 = -7 ( = 42 - 7^2), negative !

Result : 6

Due to the nature of BF language, it's far more efficient !!!

Let's start

  • Memory: N, 0, 0, 0, 0
  • Cursor: on N
  • Input: any

Process

  • Memory: N, 0, 0, current odd number, current result
  • Set current odd number to 1
  • While N is not null
    • Decrease N
    • Decrease current odd number
    • If current odd is null (else flag previously set...)
      • increase current result
      • rebuild current odd number (2 x result + 1)
  • Loop

Code

>>>+<<<                   set result and odd
[                         while N is not null
  -                       decrease N
  >>+>-                   decrease odd (and set else flag before)
  [<-]<[-                 if odd number is null (else flag trick)
    >>+                   increase result
    [-<++<+>>]<+<[->>+<<] create new odd number
  <]
<]                        loop
>>>[-]                    cleansing

Minified version

>>>+<<<[->>+>-[<-]<[->>+[-<++<+>>]<+<[->>+<<]<]<]>>>[-]

Final state

  • Memory: 0, 0, 0, 0, iSqrt(n)
  • Cursor: just before result (4th cell)
  • Input: unchanged
  • Output: unchanged

Test program

This program mixes all the previous steps : it reads an integer from the input and writes its iSqrt on the output

>,[>++++++[-<-------->]>+++++++++[<<<[->+>+<<]>>[-<<+>>]>-]<<[-<+>],]<   read integer
>>>+<<<[->>+>-[<-]<[->>+[-<++<+>>]<+<[->>+<<]<]<]>>>[-]>                 iSqrt
[>>>>++++++++++<<<<[->+>>+>-[<-]<[<<[->>>+<<<]>>>>+<<-<]<                print result
<]++++++++[->++++++<]>[-<+>]>>>>[-<<<<+>>>>]<[-]<<<]<[.<]                 ** part 2 **

We can see that this program is really shorter (and faster) than Newton's method !

Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants