# Arithmetic operators on bool type

I need to manipulate an array that can take the values -1,+1. I was thinking that it would be memory efficient to use a `Bool` array.
I also need to perform calculations, and when I operate on a `false` it gives back `0`. Is there an efficient way to make julia consider `false` as `-1`?

A `Bool` takes currently one byte (8 bit) , so it needs the same memory as a `Int8`. In your case an `Array{Int8} ` probably makes sense.

4 Likes

In that case, you’re right:) thanks!

Not really sure on what computation you envision but the easiest way is probably to directly use woolen operation such as `&`that returns a 0 (or false)

This is true for `Bool`, but the question stands with the correction that op is looking for `BitArray`.

You should probably define your own type that wraps a `BitArray`, and define arithmetic operations on it.

1 Like

Here’s a start:

``````struct FlipFlop{N} <: AbstractArray{Int8, N}
x::BitArray{N}
end

FlipFlop(x::AbstractArray) = FlipFlop(x .> 0)

size(x::FlipFlop) = size(x.x)
getindex(x::FlipFlop, i) = x.x[i] ? Int8(1) : Int8(-1)
``````

I don’t know what kind of operations you need, but this will do the basic stuff – displaying reasonably, returning a `-1` if you ask for one, and mathematics. The maths will not be optimized though, it will convert into an `Array{Int8}` on any operation. But you can redefine the operators you care about to stay in the `FlipFlop` realm.

5 Likes

Thanks for this explanation!
So if I define the math operations I need for `FlipFlop`, does this mean that the operations would be done fast? Will there be an overhead in this case?

I’m not sure. For large arrays it will be smaller in storage. A speedup would require you to either redefine broadcasting (which I don’t know how to do, or whether it’s possible for this case), or cheat by defining hard-coded broadcasts.

Here is the start of something that I think is an even better idea:

``````struct FlipFlop <: Number
x::Bool
end

FlipFlop(x::Number) = FlipFlop(x > 0)

show(io::IO, x::FlipFlop) = show(io, Int8(x.x ? 1 : -1))

convert(::Type{FlipFlop}, x::FlipFlop) = x
convert(T::Type{<:Number}, x::FlipFlop) = T(x.x ? 1 : -1)

*(x::FlipFlop, y::FlipFlop) = FlipFlop(!xor(x.x, y.x))
^(x::FlipFlop, y::Integer) = FlipFlop(x.x || y % 2 == 0)

struct FlipFlopArray{N} <: AbstractArray{FlipFlop, N}
x::BitArray{N}
end

FlipFlopArray(x::AbstractArray) = FlipFlopArray(x .> 0)

size(x::FlipFlopArray) = size(x.x)
getindex(x::FlipFlopArray, i) = FlipFlop(getindex(x.x, i))
``````

Unfortunately, currently `a.^2` is a `Vector{FlipFlop}` instead of a `FlipFlopArray`, so it will store it in a generic vector, removing the space benefit. I’m pretty sure this can be fixed by following the steps in the interfaces manual, but I haven’t quite gotten it to work yet. If someone is comfortable with this stuff, please let me know.

2 Likes

I’m actually making some headway, thanks for the fun challenge, I’m learning a lot.

Could you tell me some operations you would want to be able to do? Right now it successfully multiplies two `FlipFlopArray`s, but fails at raising one to a scalar integer.

Some benchmarking shows that the operation `a .* b` is marginally faster for `FlipFlopArray`s than `Array{Int8}`s first at about 1M elements. And even at 100M elements it’s only a small difference, so there is either something going wrong in the benchmark, or the multiplication of `Int8` arrays is just so optimized it’s hard to keep up.

Looking at allocations though, `FlipFlopArray` definitely does use less memory.

I am happy you’re having fun!!
I think I need only multiplication and addition.
I am actually interested in modeling an ising model. I know that there are some packages written for that, but I am first trying to write something of my own.

Note that flipflops aren’t an abelian group, addition of flipflops can give numbers like 0 which are not part of the set.

However, this implementation does a decent job of representing them space-efficiently, though I can’t say anything about speed (except in the case of `sum` and `prod`, which are massively improved by `FlipFlopArray`). It’s a bit rough around the edges, I’m not happy about what happens if you try to `a .+ 3` for instance, but I would guess that stuff could be ironed out with a bit of hard reading.

## Usage examples

``````julia> using FlipFlops

julia> a = rand(FlipFlop, 4)
4-element FlipFlopArray{1}:
-1
-1
-1
1

julia> b = rand(FlipFlop, 4)
4-element FlipFlopArray{1}:
-1
1
1
1

julia> a .* b
4-element FlipFlopArray{1}
1
-1
-1
1

julia> a .^ 1
4-element FlipFlopArray{1}:
-1
-1
-1
1

julia> a .^ 2
4-element FlipFlopArray{1}
1
1
1
1

julia> prod(a)
-1

julia> sum(a)
-2
``````

## Code

``````module FlipFlops
export FlipFlop, FlipFlopArray
import Base:
show,
size,
getindex,
setindex!,
convert,
*,
^,
<,
similar,
rand,
sum,
prod

struct FlipFlop <: Number
x::Bool
end

FlipFlop(x::Number) = FlipFlop(x > 0)

show(io::IO, x::FlipFlop) = show(io, Int8(x.x ? 1 : -1))

convert(::Type{FlipFlop}, x::FlipFlop) = x
convert(T::Type{<:Number}, x::FlipFlop) = T(x.x ? 1 : -1)

*(x::FlipFlop, y::FlipFlop) = FlipFlop(!xor(x.x, y.x))
^(x::FlipFlop, y::Integer) = FlipFlop(x.x || y % 2 == 0)

<(x::FlipFlop, y::Number) = <(convert(Int8, x), y)
<(x::Number, y::FlipFlop) = <(x, convert(Int8, y))

rand(::Type{FlipFlop}) = FlipFlop(rand(Bool))
rand(::Type{FlipFlop}, d::Integer, dims::Integer...) = FlipFlopArray(rand(Bool, d, dims...))

struct FlipFlopArray{N} <: AbstractArray{FlipFlop,N}
x::BitArray{N}
end

FlipFlopArray(x::AbstractArray) = FlipFlopArray(x .> 0)
FlipFlopArray(x::FlipFlopArray) = x

size(x::FlipFlopArray) = size(x.x)
getindex(x::FlipFlopArray, i) = FlipFlop(getindex(x.x, i))
function setindex!(x::FlipFlopArray, val::Number, inds::Vararg{Int,N}) where {N}
return setindex!(x.x, val .> 0, inds...)
end

struct FlipFlopStyle{N} <: Broadcast.AbstractArrayStyle{N} end # If FlipFlopArray is broadcasted with anything not explicitly FlipFlop-y, use as an array
return FlipFlopStyle{N}()
end # Broadcasting with a scalar, FlipFlop wins
return FlipFlopStyle{N}()
end