4

I am trying to do this in Bash:

read n

echo int(math.ceil((math.sqrt(1 + 8 * n) - 1) / 2))

Of course this isn't working syntax but I am just putting it there so you can tell what I am trying to do.

Is there an easy way to actually make this into valid Bash?

user8926565
  • 87
  • 6
  • 1
    There's certainly no `sqrt` operator in `bash`. – Brett Hale Nov 12 '17 at 04:09
  • Do I have to write my own sqrt function? – user8926565 Nov 12 '17 at 04:10
  • Not sure if it helps, but since `(8n + 1)` is odd, then if `sqrt(8n + 1)` is an integral value, it must also be odd. Consequently, subtracting `(1)` and dividing by `(2)` will always be integral. So if `(n)` can be expressed as `k(k + 1)/2` for any integer `(k)`, then the result is an integer. Otherwise, add one to the integer part. – Brett Hale Nov 12 '17 at 04:50
  • @BrettHale Yes, definitely one way around it; wanted to generalize though so in the future if I wanted to compute sqrt's I'd be able to – user8926565 Nov 12 '17 at 04:52
  • And my comment doesn't really help, since finding that `(k)` value is essentially the same as your original problem! – Brett Hale Nov 12 '17 at 05:13

3 Answers3

2

Although you ask to do this in Bash, there's no native support for functions like square root or ceiling. It would be simpler to delegate to Perl:

perl -wmPOSIX -e "print POSIX::ceil((sqrt(1 + 8 * $n) - 1) / 2)"

Alternatively, you could use bc to calculate the square root, and some Bash to calculate the ceiling.

Let's define a function that prints the result of the formula with sqrt of bc:

formula() {
    local n=$1
    bc -l <<< "(sqrt(1 + 8 * $n) - 1) / 2"
}

The -l flag changes the scale from the default 0 to 20. This affects the scale in the display of floating point results. For example, with the default zero, 10 / 3 would print just 3. We need the floating point details in the next step to compute the ceiling.

ceil() {
    local n=$1
    local intpart=${n%%.*}
    if [[ $n =~ \.00*$ ]]; then
        echo $intpart
    else
        echo $((intpart + 1))
    fi
}

The idea here is to extract the integer part, and if the decimal part is all zeros, then we print simply the integer part, otherwise the integer part + 1, as that is the ceiling.

And a final simple function that combines the above functions to get the result that you want:

compute() {
    local n=$1
    ceil $(formula $n)
}

And a checker function to test it:

check() {
    local n num
    for n; do
        num=$(formula $n)
        echo $n $num $(compute $n)
    done
}

Let's try it:

check 1 2 3 4 7 11 12 16 17

It produces:

1 1.00000000000000000000 1
2 1.56155281280883027491 2
3 2.00000000000000000000 2
4 2.37228132326901432992 3
7 3.27491721763537484861 4
11 4.21699056602830190566 5
12 4.42442890089805236087 5
16 5.17890834580027361089 6
17 5.35234995535981255455 6
janos
  • 120,954
  • 29
  • 226
  • 236
1

You can use bc's sqrt function.

echo "(sqrt(1 + 8 * 3) - 1) / 2" | bc

Ceil function can be implemented using any of the methods described in this answer.

Getting Ceil integer

For eg: 

  ceiling_divide() {
      ceiling_result=`echo "($1 + $2 - 1)/$2" | bc`
    }
Kaushik Nayak
  • 30,772
  • 5
  • 32
  • 45
1

You can use bc for all the job

$>cat filebc

print "Enter a number\n";
scale=20
a=read()
b=((sqrt(1 + 8 * a) - 1) / 2)
scale=0
print "ceil = ";
((b/1)+((b%1)>0))
quit

Call it like that

bc -q filebc
ctac_
  • 2,413
  • 2
  • 7
  • 17