Home > Archive > Fortran > March 2008 > two graycode functions: always same result?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
two graycode functions: always same result?
|
|
| Bart Vandewoestyne 2008-03-13, 10:17 pm |
| Hello,
In a laboratory session, i asked my students to implement a
function that returns the Graycode of an integer. The model
solution I had in mind was the following:
elemental function graycode(n) result (y)
integer(kind=i4b), intent(in) :: n
integer(kind=i4b) :: y
y = ieor(n, ishft(n, -1))
end function graycode
some students came up with the following, slightly different solution:
elemental function graycode2(n) result (y)
integer(kind=i4b), intent(in) :: n
integer(kind=i4b) :: y
y = ieor(n, n/2)
end function graycode2
At first sight, this looks like it's doing the same, but being sceptical
as I am, I was wondering if under standard-conforming Fortran 95, these two
functions will *always* produce the same result... so I wrote the following testprogram:
program test_graycode
integer, parameter :: i4b = selected_int_kind(9)
integer(kind=i4b) :: i
do i = 1,huge(1_i4b)
if (modulo(i, 100000000) == 0) then
print *, huge(1_i4b)
print *, i
end if
if (graycode(i) /= graycode2(i)) then
print *, "Found a difference at ", i, "!"
stop
end if
end do
contains
! Return the Gray code of n. Method 1.
!
elemental function graycode(n) result (y)
integer(kind=i4b), intent(in) :: n
integer(kind=i4b) :: y
y = ieor(n, ishft(n, -1))
end function graycode
! Return the Gray code of n. Method 2.
!
elemental function graycode2(n) result (y)
integer(kind=i4b), intent(in) :: n
integer(kind=i4b) :: y
y = ieor(n, n/2)
end function graycode2
end program test_graycode
and apparently, with my compiler and on my computer, i do get the same result
for i=1,huge(1_i4b).
But I was wondering if there could be circumstances where the result will
not be the same, even when the code is standard Fortran 95 conforming.
Could it depend on the rounding mode too?
Greetzzz,
Bart
--
"Share what you know. Learn what you don't."
| |
| Richard Maine 2008-03-13, 10:17 pm |
| Bart Vandewoestyne <MyFirstName.MyLastName@telenet.be> wrote:
> y = ieor(n, ishft(n, -1))
....
> y = ieor(n, n/2)
....
> But I was wondering if there could be circumstances where the result will
> not be the same, even when the code is standard Fortran 95 conforming.
I've elided all but the two differing lines above. Your question appears
to reduce to the simpler question of whether ishft(n,-1) is always the
same as n/2. For non-negative n, the answer is that the two are always
the same. See the definition of ishft, along with that of the bit model
used by ishft.
In particular, note that the bit model does *NOT* depend on the physical
representation of integers; any material relating to such physical
representation is irrelevant. The definition of ishft is such that
ishft(n,-1) is always n/2, regardless of what the physical bits of n and
n/2 might look like. For a binary machine, those bits will indeed look
shifted. On something like a decimal machine, they won't, but that's
still the definition of ishft.
This is all for non-negative n only. For negative n, the results of any
of the bit operations (such as ishft) are processor-dependent.
> Could it depend on the rounding mode too?
I don't know why you would even bring that up. No, it doesn't. It also
doesn't depend on the phase of the moon.
The rounding mode has to do with floating point. There isn't a floating
point entity in sight in this code. I suppose you might possibly be
thinking that some rounding modes might cause, for example, 7/2 to
evaluate as 4 instead of 3. No, they don't. They have nothing to do with
integer arithmetic.
--
Richard Maine | Good judgement comes from experience;
email: last name at domain . net | experience comes from bad judgement.
domain: summertriangle | -- Mark Twain
| |
| jamesgiles@att.net 2008-03-13, 10:17 pm |
| If the numerator is positive, then dividing by a power of two is
guaranteed identical to right shifting the bit model by the
appropriate power. If the numerator is negative that might not be the
case. If your implementation is 2's complement, right shift (with
sign fill) of a negative value is identical to a divide that truncates
away from zero. Fortran integer divide *must* truncate toward zero
(there are no rounding modes for integer arithmetic in the standard,
hence only one conforming behavior is described).
In 1's complement, right (with sign fill) matches the behavior of
divide by powers of two for both positive and negative numerators.
Signed magnitude implementations won't match divide (unless the shift
preserves the sign but doesn't fill with it).
Integer implementations with a different radix than two have to
simulate one of the above for the bit-wise operations anyway (at
least, that's how I hope the standard works).
--
J. Giles
"I conclude that there are two ways of constructing a software
design: One way is to make it so simple that there are obviously
no deficiencies and the other way is to make it so complicated
that there are no obvious deficiencies." -- C. A. R. Hoare
| |
| Bart Vandewoestyne 2008-03-13, 10:17 pm |
| On 2008-03-13, Richard Maine <nospam@see.signature> wrote:
>
> I've elided all but the two differing lines above. Your question appears
> to reduce to the simpler question of whether ishft(n,-1) is always the
> same as n/2. For non-negative n, the answer is that the two are always
> the same. See the definition of ishft, along with that of the bit model
> used by ishft.
>
> In particular, note that the bit model does *NOT* depend on the physical
> representation of integers; any material relating to such physical
> representation is irrelevant. The definition of ishft is such that
> ishft(n,-1) is always n/2, regardless of what the physical bits of n and
> n/2 might look like. For a binary machine, those bits will indeed look
> shifted. On something like a decimal machine, they won't, but that's
> still the definition of ishft.
OK. I have also looked at the latest draft of the Fortran 95
standard and how you describe it is actually how i thought it
was. Thanks for confirming :-)
> This is all for non-negative n only. For negative n, the results of any
> of the bit operations (such as ishft) are processor-dependent.
OK.
>
> I don't know why you would even bring that up. No, it doesn't. It also
> doesn't depend on the phase of the moon.
:-)
> The rounding mode has to do with floating point. There isn't a floating
> point entity in sight in this code. I suppose you might possibly be
> thinking that some rounding modes might cause, for example, 7/2 to
> evaluate as 4 instead of 3.
Indeed, that was exactly what I had in mind...
> No, they don't. They have nothing to do with integer arithmetic.
OK. I indeed mis floating point arithmetic with integer
arithmetic here. IIRC, the way integer division works is also
specified by the standard and it has nothing to do with floating
point rounding modes.
Thanks for your answers and clarifications,
Bart
--
"Share what you know. Learn what you don't."
|
|
|
|
|