http://www.perlmonks.org?node_id=180320

One thing I have always wanted (in every language I've used except assembler) is a function that returned both result and remainder of an integer division.

Both are usually calculated and left in seperate cpu registers after a DIV instruction, but I am forced by to use "/" and "%" to get at them, which means that the division is being done twice.

I did once create a function using in-line assembler in C to do this, but the single return value from a C function meant that the function was messy to use.

Perl's natural ability to return a list and assign lists mean that the idea resurrected itself in my brain when I saw this post and the answers to it.

My solution to this was:

use strict; sub div_mod { return int( $_[0]/$_[1]) , ($_[0] % $_[1]); } my $i = 1332443; my ( $s, $m, $h, $d ); ($m,$s) = div_mod($i, 60); ($h,$m) = div_mod($m, 60); ($d,$h) = div_mod($h, 24); print "$d days, $h hours, $m minutes, $s seconds.\n";

Which I think is rather elegant, but still possible less efficient than the other solutions, and less efficient than it could be as I am still performing the division twice to get at the information.

I took a look at the inline-c stuff, but that doesn't help for the same reasons.

I also took a quick look at the overloading capabilities but I am not familiar enough with Perl to understand that yet.

I am wondering if it is possible to define a new operator for Perl? Maybe "/%" that would do the same thing as my div_mod() sub in the code above but accessing the appropriate registers to save a division?

Possibly better (and more Perlish) would be to have both values returned only if the mod (%) operator was called in a LIST context, especially as mod (%) is an inherently integer operator?

Does this have any merit? If so, would this have to be done deep in the guts of the compiler/interpreter or could it be added as a module in some way?

Replies are listed 'Best First'.
(jeffa) Re: A better mod (%) operator?
by jeffa (Bishop) on Jul 08, 2002 at 21:46 UTC
    I almost have a working example with overload, but i can't get it to work - wantarray is being fussy with me. The problem with overload though, is that you cannot define some new token such as /% - you have to use an existing one. This should get you started, but like i said, it doesn't work. I have provided a subroutine at the bottom that does work, i would appreciate it if someone could tell me what i did wrong. I chose * as the overloaded operator just to show that the overload sub is being called, i originally used %
    package mod; use strict; use overload '*' => sub { my $div = int(${$_[0]} / ${$_[1]}); my $mod = ${$_[0]} % ${$_[1]}; return wantarray ? ($div,$mod) : $mod; }; sub new { my ($class,$val) = @_; return bless \$val, $class; } package main; use strict; my $i = mod->new(90); my $j = mod->new(60); my @x = $i * $j; my $x = $i * $j; print "@x\n"; print "$x\n"; my @y = mod(90,60); my $y = mod(90,60); print "@y\n"; print "$y\n"; sub mod { my $div = int($_[0] / $_[1]); my $mod = $_[0] % $_[1]; return wantarray ? ($div,$mod) : $mod; }; __END__ yields: 30 <-- this should be 1 30 30 1 30 30

    jeffa

    L-LL-L--L-LL-L--L-LL-L--
    -R--R-RR-R--R-RR-R--R-RR
    B--B--B--B--B--B--B--B--
    H---H---H---H---H---H---
    (the triplet paradiddle with high-hat)
    

      It seems that wantarray() always returns false in an overloading sub. At least that is what happened in Overloading for List Context.

      A bug perhaps?

      --
      John.

        The problem isn't with wantarry, it's something more low level then that, observe a slightly modified version that doesn't use wantarray...

        use overload '*' => sub { my $div = int(${$_[0]} / ${$_[1]}); my $mod = ${$_[0]} % ${$_[1]}; return ($div, $mod); };

        This still generates "30" for 90/30, regardless of context ... it's as if overloaded operators are allways called in some sort of bizarro scalar context where lists are evaluated as their last element instead of their length...

        package mod; use strict; use overload '*' => sub { return ('yakko', 'wakko', 'dot'); }; sub new { my ($class,$val) = @_; return bless \$val, $class; } package main; use strict; my $i = mod->new(90); my $j = mod->new(60); my @x = $i * $j; my $x = $i * $j; print "@x\n"; print "$x\n"; __END__ dot dot

        Update: My bad, I totally spaced out on the fact that lists in scalar context evaluate to the last element... i was thinking of it just like an array.

      The problem with overload though, is that you cannot define some new token such as /% - you have to use an existing one.
      perl 6 solves this problem. something like:

      my sub operator:%/ is prec(\&operator:%) ($x, $y) { ... }
      i'll be glad i can finally add the ,= operator i've been looking for to replace push.

      ~Particle *accelerates*

        Oooooooo....this is going to be SUCH a boon to the Perl Obfuscators :)

        Kickstart

      Thanks Jeffa.

      It looks as if you are being bitten by an "undocumented feature" of wantarray(). Rest assured though your efforts were not wasted, this small sample has assisted my education at least.

      With regard to the code. If I understand what I am seeing, the overloaded operator will only be called if the variables to which its applied have been blessed into the package in which the overloading is done by the use of new()?

      I assume from this that there is no way to overload an operator such that it will operate without requiring this?

        Yep, you have to have a blessed package (an object) in order for overload to work - but who says you can't bless main? ;)
        use strict; use overload '+' => sub { ${$_[0]} - ${$_[1]} }; use overload '-' => sub { ${$_[0]} + ${$_[1]} }; my ($x,$y) = (90,60); my $i = bless \$x, 'main'; my $j = bless \$y, 'main'; # objects use overloaded operators print $i + $j, $/; # 30 print $i - $j, $/; # 150 # normal scalars use Perl operators print $x + $y, $/; # 150 print $x - $y, $/; # 30

        jeffa

        L-LL-L--L-LL-L--L-LL-L--
        -R--R-RR-R--R-RR-R--R-RR
        B--B--B--B--B--B--B--B--
        H---H---H---H---H---H---
        (the triplet paradiddle with high-hat)
        
      Too bad Perl doesn't use a few other math symbols from Unicode as operator tokens (with no built-in meaning). I think that would be very easy to add. Often what's needed is a "different flavor" of multiplication etc., so using the circled cross etc. would be good choices, and they can have the same precidence as their ordinary cousins.

        Which key would I use to type that operator in vi? :)
Re: A better mod (%) operator?
by rinceWind (Monsignor) on Jul 08, 2002 at 23:29 UTC
    If you take a look at Math::BigInt, you will find that the method bdiv in list context returns quotient and remainder.
    SYNOPSIS use Math::BigInt; $i = Math::BigInt->new($string); $i->bneg return BINT negation $i->babs return BINT absolute value $i->bcmp(BINT) return CODE compare numbers (undef,<0,=0,>0) $i->badd(BINT) return BINT addition $i->bsub(BINT) return BINT subtraction $i->bmul(BINT) return BINT multiplication $i->bdiv(BINT) return (BINT,BINT) division (quo,rem) just quo if sc +alar $i->bmod(BINT) return BINT modulus $i->bgcd(BINT) return BINT greatest common divisor $i->bnorm return BINT normalization $i->blsft(BINT) return BINT left shift $i->brsft(BINT) return (BINT,BINT) right shift (quo,rem) just quo if + scalar $i->band(BINT) return BINT bit-wise and $i->bior(BINT) return BINT bit-wise inclusive or $i->bxor(BINT) return BINT bit-wise exclusive or $i->bnot return BINT bit-wise not
    Although it's a bit slow and clunky, Math::BigInt's overload mechanism makes a good attempt at a drop-in replacement for n bit integers.
Re: A better mod (%) operator?
by tadman (Prior) on Jul 08, 2002 at 21:15 UTC
    There's nothing to stop you from using Inline::C, with assembler, to make it all happen. The catch is that you have to construct an array which you return to Perl, so it would be wise to read up on how XS works. The thing is, though, that the cost of manufacturing an array vastly exceeds any speed gain you'd get by using inline assembler. These days, division isn't nearly as expensive as it used to be, and memory is often the bottleneck.

    I think if you're that concerned about speed, though, you wouldn't be using Perl anyway. You'd be using C, or C++, or possibly even FORTRAN.

      It wasn't really a "search for speed" that drove the thought, it was more elegance, orthogonality and that it bugs me that I know that the 'other part of the equation' is sitting there in a register somewhere but I have to do the division again to get it.

      Down the years, It seems that almost every time I have made use of the mod operator, I have also done a div with the same parameters.

      Finally using Perl, I have a language that could elegantly provide me with both halves of the equation in one pass and render the elegance that comes with it.

      I hadn't thought about the expense of constructing the return list. Is it possible to "re-use" the inbound @_ list? Would there be any benefit in doing so?

      I wonder how constructing a new list would compare (at the inner levels) with duplicating the whole inbound/outbound stack frames etc.? Possibly little in it?

      Basically, I don't yet know enough to judge and am not ready to go digging deep enough to get the answers.

      T'was just an idea:^).

      Or better yet, Inline::ASM.

      But I agree with your other statements - I'd be very surprised to find a Perl program where a division operation was a significant bottleneck.

      -sam

        From the Inline::ASM documentation:
        WARNING

        Do NOT use assembler to write Perl extensions! It's sick and wrong!
        Better. Evil. Muhahaha.
Re: A better mod (%) operator?
by Abigail-II (Bishop) on Jul 09, 2002 at 09:19 UTC
    Having % return a two element list in list context would not be a good idea. Any function call of the form
    func $var1 % $var2
    (where func isn't prototyped) would suddenly do something the author didn't intend.

    Abigail

      Amazing how obvious things are when someone shoves them under your nose:( That knocks that idea on the head.

      I guess its wait for Perl 6 and use /% or %% or some such, and stick with my inefficient-but-elegant sub solution for now.

Re: A better mod (%) operator?
by mattr (Curate) on Jul 09, 2002 at 05:29 UTC
    You might be interested in Bit::Vector which according to its homepage uses Perl for overloading but implements the object methods (e.g. Divide and GCD) in C. Interesting bit (sorry) about Euclid's Theorem.

    You may also like to have fun with the integer pragma.

certainly has merit
by hding (Chaplain) on Jul 09, 2002 at 00:19 UTC
    It is certainly a sensible thing to want. Common Lisp provides this via multiple return values and the functions floor, ceiling, truncate, and round, for example. I'm not enough of a Perl guy to know what the best way to do it in Perl would be.
Re: A better mod (%) operator?
by shotgunefx (Parson) on Jul 09, 2002 at 10:37 UTC
    You could look at Filter::Simple as well. Then you could swap
    ($m,$s) = $i /% 60 with ($m,$s) = div_mod($i,60).

    Though trying to parse the left hand side of /% for anything that would constitute a valid expression would be a real pain.

    -Lee

    "To be civilized is to deny one's nature."
Re: A better mod (%) operator?
by John M. Dlugosz (Monsignor) on Jul 09, 2002 at 20:10 UTC
    That's bugged me too, especially in the old days when a division took 130 clocks at 12MHz.

    I hope that the optomizer can take care of it. So, I do the common expressions into temp variables, and then do both / and % with identical parameters on concecutive lines.

Re: A better mod (%) operator?
by fglock (Vicar) on Jul 10, 2002 at 19:01 UTC

    This is something I used in the old times when multiplication was much faster than division:

    sub divmod { use integer; my ($a, $b) = @_; my $tmp = $a / $b; ($tmp, $a - ($b * $tmp) ); } $a = 13; $b = 2; print divmod($a, $b);

    This is much more interesting to do in assembler then in Perl (maybe Parrot?)

Re: A better mod (%) operator?
by hdb (Monsignor) on Jan 10, 2014 at 20:13 UTC

    If you are happy to lose the original numerator, you could do it with side effects on the arguments. The original numerator would become the result of div and the function itself would return the remainder. (Just for the fun of it in autoboxing notation...)

    use strict; use warnings; my $rdiv = sub { my $num = $_[0]; $_[0] = int( $_[0]/$_[1] ); $num - $ +_[0]*$_[1] }; my $x = 11; my $y = 4; my $r = $x->$rdiv( $y ); print "$x, $r\n";
      you could do it with side effects on the arguments.

      That kind of defeats the original purpose of utilising the fact that -- for every processor I'm knowledgeable of; though that's not a huge sample -- at the machine code level, DIV instructions produce both quotient and remainder as the result of a single operation.

      From the Intel manual:

      DIV—Unsigned Divide

      Description: Divides unsigned the value in the AX, DX:AX, EDX:EAX, or RDX:RAX registers (divi- dend) by the source operand (divisor) and stores the result in the AX (AH:AL), DX:AX, EDX:EAX, or RDX:RAX registers.

      The two operations of finding quotient and remainder of one number divided by another are so often used in concert with each other, it seems a waste to have to perform the division twice to get at both parts.

      (Just for the fun of it in autoboxing notation...)

      Yuck! What a waste of cpu :)


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.