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 FlipFlopArrays, but fails at raising one to a scalar integer.

Some benchmarking shows that the operation a .* b is marginally faster for FlipFlopArrays 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,
    BroadcastStyle,
    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
BroadcastStyle(::Type{<:FlipFlopArray{N}}) where {N} = FlipFlopStyle{N}()
function BroadcastStyle(::FlipFlopStyle{N}, ::Broadcast.AbstractArrayStyle{0}) where {N}
    return FlipFlopStyle{N}()
end # Broadcasting with a scalar, FlipFlop wins
function BroadcastStyle(::FlipFlopStyle{N}, ::Broadcast.DefaultArrayStyle{0}) where {N}
    return FlipFlopStyle{N}()
end

function similar(bc::Broadcast.Broadcasted{FlipFlopStyle{N}}, ::Type{FlipFlop}) where {N}
    return FlipFlopArray(similar(BitArray, axes(bc)))
end

function similar(bc::Broadcast.Broadcasted{FlipFlopStyle{N}}, ::Type{Bool}) where {N}
    return FlipFlopArray(similar(Bitarray, axes(bc)))
end

sum(x::FlipFlopArray) = 2 * count(x.x) - length(x)
prod(x::FlipFlopArray) = 1 - 2 * ((count(x.x) + length(x)) % 2)

end
3 Likes