Sunday, February 13, 2011

Correctly over-loading a stringbuf to replace cout in a MATLAB mex file

MathWorks currently doesn't allow you to use cout from a mex file when the MATLAB desktop is open because they have redirected stdout. Their current workaround is providing a function, mexPrintf, that they request you use instead. After googling around a bit, I think that it's possible to extend the std::stringbuf class to do what I need. Here's what I have so far. Is this robust enough, or are there other methods I need to overload or a better way to do this? (Looking for portability in a general UNIX environment and the ability to use std::cout as normal if this code is not linked against a mex executable)

class mstream : public stringbuf {
public:
  virtual streamsize xsputn(const char *s, std::streamsize n) 
  {
mexPrintf("*s",s,n);
return basic_streambuf<char, std::char_traits<char>>::xsputn(s,n);
  }
}; 

mstream mout;
outbuf = cout.rdbuf(mout.rdbuf());
  • cout is a particular character output stream. If you want a cout that writes to a file, use an fstream, particularly an ofstream. They have the same interface that cout provides. Additionally, if you want to grab their buffer (with rdbuf) you can.

  • You don't really want to overload std::stringbuf, you want to overload std::streambuf or std::basic_streambuf (if you want to support multiple character types), also you need to override the overflow method as well.

    But I also think you need to rethink your solution to your problem.

    cout is just a ostream, so if all classes / functions takes a ostream then you can pass in anything you like. e.g. cout, ofstream, etc

    If that's too hard then I would create my own version of cout, maybe called mycout that can be defined at either compiler time or runtime time (depending on what you want to do).

    A simple solution may be:

    #include <streambuf>
    #include <ostream>
    
    class mystream : public std::streambuf
    {
    public:
        mystream() {}
    
    protected:
        virtual int_type overflow(int_type c)
        {
            if(c != EOF)
            {
                char z = c;
                mexPrintf("%c",c);
                return EOF;
            }
            return c;
        }
    
        virtual std::streamsize xsputn(const char* s, std::streamsize num)
        {
            mexPrintf("*s",s,n);
            return num;
        }
    };
    
    class myostream : public std::ostream
    {
    protected:
        mystream buf;
    
    public:
        myostream() : std::ostream(&buf) {}
    };
    
    myostream mycout;
    

    And the cout version could just be:

    typedef std::cout mycout;
    

    A runtime version is a bit more work but easily doable.

  • Shane, thanks very much for your help. Here's my final working implementation.

    class mstream : public std::streambuf {
    public:
    protected:
      virtual std::streamsize xsputn(const char *s, std::streamsize n); 
      virtual int overflow(int c = EOF);
    };
    

    ...

    std::streamsize 
    mstream::xsputn(const char *s, std::streamsize n) 
    {
      mexPrintf("%.*s",n,s);
      return n;
    }
    
    int 
    mstream::overflow(int c) 
    {
        if (c != EOF) {
          mexPrintf("%.1s",&c);
        }
        return 1;
    }
    

    ...

    mstream mout;
    std::streambuf outbuf = std::cout.rdbuf(&mout);
    

    ...

    std::cout.rdbuf(outbuf);
    
    From

T-Sql cursor not proceeding on fetch

Hi,I know that cursors are frowned upon and I try to avoid their use as much as possible, but there may be some legitimate reasons to use them. I have one and I am trying to use a pair of cursors: one for the primary table and one for the secondary table. The primary table cursor iterates through the primary table in an outer loop. the secondary table cursor iterates through the secondary table in the inner loop. The problem is, that the primary table cursor though apparently proceeding and saving the primary key column value [Fname] into a local variable @Fname, but it does not get the row for the corresponding foreign key column in the secondary table. For the secondary table it always returns the rows whose foreign key column value matches the primary key column value of the first row of the primary table.

Following is a very simplified example for what I want to do in the real stored procedure. Names is the primary table

SET NOCOUNT ON
DECLARE 
    @Fname varchar(50) -- to hold the fname column value from outer cursor loop
    ,@FK_Fname varchar(50) -- to hold the fname column value from inner cursor loop
    ,@score int
;

--prepare primary table to be iterated in the  outer loop
DECLARE @Names AS Table (Fname varchar(50))
INSERT @Names
    SELECT 'Jim' UNION
    SELECT 'Bob' UNION
    SELECT 'Sam' UNION
    SELECT 'Jo' 


--prepare secondary/detail table to be iterated in the inner loop
DECLARE @Scores AS Table (Fname varchar(50), Score int)
INSERT @Scores
    SELECT 'Jo',1 UNION
    SELECT 'Jo',5 UNION
    SELECT 'Jim',4 UNION
    SELECT 'Bob',10 UNION
    SELECT 'Bob',15 

--cursor to iterate on the primary table in the outer loop
DECLARE curNames CURSOR
FOR SELECT Fname FROM @Names


OPEN curNames
FETCH NEXT FROM curNames INTO @Fname

--cursor to iterate on the secondary table in the inner loop
DECLARE curScores CURSOR
FOR 
    SELECT FName,Score 
    FROM @Scores 
    WHERE Fname = @Fname 
 --*** NOTE: Using the primary table's column value @Fname from the outer loop

WHILE @@FETCH_STATUS = 0
BEGIN
    PRINT 'Outer loop @Fname = ' + @Fname

    OPEN curScores
    FETCH NEXT FROM curScores INTO @FK_Fname, @Score

    WHILE @@FETCH_STATUS = 0
    BEGIN
     PRINT ' FK_Fname=' + @FK_Fname + '. Score=' + STR(@Score)
     FETCH NEXT FROM curScores INTO @FK_Fname, @Score
    END
    CLOSE curScores
    FETCH NEXT FROM curNames INTO @Fname
END

DEALLOCATE curScores

CLOSE curNames
DEALLOCATE curNames

Here is what I get for the result. Please note that for the outer loop it DOES show the up-to-date Fname, but when that Fname is used as @Fname to fetch the relevant row from the secondary table for the succeeding iterations, it still get the rows that match the first row (Bob) of the primary table.

Outer loop @Fname = Bob
    FK_Fname=Bob. Score=10
    FK_Fname=Bob. Score=15
Outer loop @Fname = Jim
    FK_Fname=Bob. Score=10
    FK_Fname=Bob. Score=15
Outer loop @Fname = Jo
    FK_Fname=Bob. Score=10
    FK_Fname=Bob. Score=15
Outer loop @Fname = Sam
    FK_Fname=Bob. Score=10
    FK_Fname=Bob. Score=15

Please let me know what am I do wrong. Thanks in advance!

  • I'd try placing the

    DECLARE curScores CURSOR
    FOR 
        SELECT FName,Score 
        FROM @Scores 
        WHERE Fname = @Fname
    

    inside the first while, beacuse you're declaring the cursor only for the first name value

  • The value of @fName is evaluated at :DECLARE curScores CURSOR and not in the primary loop. You must Declare and then deallocate the secon cursor in the primary loop.

    Aamir Ghanchi : Thanks Ovidiu. that did the trick!
  • Thanks to few hints, I was able to find the solution.

    I had to DECLARE and DEALLOCATE the secondary cursor within the first loop. I initially hated to do it as I thought alocating and deallocating resources in the loop was not a good idea, but I think there is no other way to avoid this in this particular situation. Noew the working code looks some thing like this:

    SET NOCOUNT ON
    DECLARE 
        @Fname varchar(50) -- to hold the fname column value from outer cursor loop
        ,@FK_Fname varchar(50) -- to hold the fname column value from inner cursor loop
        ,@score int
    ;
    
    --prepare primary table to be iterated in the  outer loop
    DECLARE @Names AS Table (Fname varchar(50))
    INSERT @Names
        SELECT 'Jim' UNION
        SELECT 'Bob' UNION
        SELECT 'Sam' UNION
        SELECT 'Jo' 
    
    
    --prepare secondary/detail table to be iterated in the inner loop
    DECLARE @Scores AS Table (Fname varchar(50), Score int)
    INSERT @Scores
        SELECT 'Jo',1 UNION
        SELECT 'Jo',5 UNION
        SELECT 'Jim',4 UNION
        SELECT 'Bob',10 UNION
        SELECT 'Bob',15 
    
    --cursor to iterate on the primary table in the outer loop
    DECLARE curNames CURSOR
    FOR SELECT Fname FROM @Names
    
    
    OPEN curNames
    FETCH NEXT FROM curNames INTO @Fname
    
    --cursor to iterate on the secondary table in the inner loop
    DECLARE curScores CURSOR
    FOR 
        SELECT FName,Score 
        FROM @Scores 
        WHERE Fname = @Fname 
     --*** NOTE: Using the primary table's column value @Fname from the outer loop
    
    WHILE @@FETCH_STATUS = 0
    BEGIN
        PRINT 'Outer loop @Fname = ' + @Fname
    
        OPEN curScores
        FETCH NEXT FROM curScores INTO @FK_Fname, @Score
    
        WHILE @@FETCH_STATUS = 0
        BEGIN
            PRINT ' FK_Fname=' + @FK_Fname + '. Score=' + STR(@Score)
            FETCH NEXT FROM curScores INTO @FK_Fname, @Score
        END
        CLOSE curScores
        FETCH NEXT FROM curNames INTO @Fname
    END
    
    DEALLOCATE curScores
    
    CLOSE curNames
    DEALLOCATE curNames
    

    And I am getting the right results:

    Outer loop @Fname = Bob
        FK_Fname=Bob. Score=        10
        FK_Fname=Bob. Score=        15
    Outer loop @Fname = Jim
        FK_Fname=Jim. Score=         4
    Outer loop @Fname = Jo
        FK_Fname=Jo. Score=         1
        FK_Fname=Jo. Score=         5
    Outer loop @Fname = Sam
    
  • I think you could do this so much easier with temp tables that have row numbers:

    create table #temp1
    (
     row int identity(1,1)
     , ... 
    )
    

    It really looks like you're asking SQL to behave like a language that likes loops. It doesn't. Whenever I find myself writing a loop in SQL I ask myself, does it have to be done this way? 7/10 times the answer is no, I can do it with sets instead.

    From jcollum

Optimal data architecture for tagging, clouds, and searching (like StackOverflow)?

I'd love to know how Stack Overflow's tagging and search is architected, because it seems to work pretty well.

What is a good database/search model if I want to do all of the following:

  1. Storing Tags on various entities, (how normalized? i.e. Entity, Tag, and Entity_Tag tables?)
  2. Searching for items with particular tags
  3. Building a tag cloud of all tags that apply to a particular search result set
  4. How to show a tag list for each item in a search result?

Perhaps it makes sense to store the tags in a normalized form, but also as a space-delimited string for the purposes of #2, #4, and perhaps #3. Thoughts?

I have heard it said that Stack Overflow uses Lucene for search. Is that true? I've heard a couple of podcasts discussing SQL optimization, but nothing about Lucene. If they do use Lucene, I'm wondering how much of the search result comes from Lucene, and whether the "drill-down" tag cloud comes from Lucene.

  • I don't know if they qualify as optimal, but both DotNetKicks and Kigg are open source digg clone implementations. You can look at how they're doing tags and search.

    My best guesses without a lot of deliberation :)

    1. I never like the idea of serializing multiple values into a single field, so delimited strings stored in one field don't appeal to me... might work for adjacency paths with trees, but those are always ordered and tags need not be. This seems like it would tax the LIKE operator work you might do to find them.

    So my initial take is probably Entity -> EntityTag <- Tag.

    1. This approach makes finding items via Tag pretty easy, join back through EntityTag, call it a day.

    2. You need a secondary operation here to select the distinct tags for the result set. So a.) pull the result set, b.) normalize the tag space. I think you do this no matter what the answer is to #1 -- even stuffing tags into one field will still yield duplicate tags (and you have to deserialize them to perform this op--so more work, another argument for a fully relational approach).

    3. Still easy. Here's one area where the serialized approach works better. No need to join for child tags, it's right there in the Entity. That said, pulling out 0..n tags via the two table join doesn't seem too challenging to me. If you're talking perf considerations, build it normalized first then optimize via cache or denorm.

    The other option is "do both". This feels like a premature optimization, but you could do the full normalized approach to support any tag-centric operations and serialize upon persist to have a denormalized version right there in the Entity. A bit more work, some potential to fall out of synch if not fully covered, but best of both worlds if there's real limitations to the fully normalized way in your use cases.

    Lucene is interesting as well, you can declare specific metadata in the indices IIRC, so you could potentially leverage tag search this way as well. My suspicion is, if you go too far down this road, then you end up having some disconnects between what you store in the database and the index at some point. I can speak favorably about Lucene, it's very capable and easy to use--I believe .Text used it for it's search capabilities and it supported all of weblogs.asp.net prior to it switching over to Community Server. I'd stick to it for full-text search if MSSQL isn't in the picture/sufficient, solve the tag issues in the database imo.

    From Grant
  • Wow I just wrote a big post and SO choked and hung on it, and when I hit my back button to resubmit, the markup editor was empty. aaargh.

    So here I go again...

    Regarding Stack Overflow, it turns out that they use SQL server 2005 full text search.

    Regarding the OS projects recommended by @Grant:

    • *DotNetKicks uses the DB for tagging and Lucene for full-text search. There appears to be no way to combine a full text search with a tag search
    • Kigg uses Linq-to-SQL for both search and tag queries. Both queries join Stories->StoryTags->Tags.
    • Both projects have a 3-table approach to tagging as everyone generally seems to recommend

    I also found some other questions on SO that I'd missed before:

    What I'm currently doing for each of the items I mentioned:

    1. In the DB, 3 tables: Entity, Tag, Entity_Tag. I use the DB to:
      • Build site-wide tag clouds
      • browse by tag (i.e. urls like SO's /questions/tagged/ASP.NET)
    2. For search I use Lucene + NHibernate.Search
      • Tags are concat'd into a TagString that is indexed by Lucene
        • So I have the full power of the Lucene query engine (AND / OR / NOT queries)
        • I can search for text and filter by tags at the same time
        • The Lucene analyzer merges words for better tag searches (i.e. a tag search for "test" will also find stuff tagged "testing")
      • Lucene returns a potentially enormous result set, which I paginate to 20 results
      • Then NHibernate loads the result Entities by Id, either from the DB or the Entity cache
      • So it's entirely possible that a search results in 0 hits to the DB
    3. Not doing this yet, but I think I will probably try to find a way to build the tag cloud from the TagString in Lucene, rather than take another DB hit
    4. Haven't done this yet either, but I will probably store the TagString in the DB so that I can show an Entity's Tag list without having to make 2 more joins.

    This means that whenever an Entity's tags are modified, I have to:

    • Insert any new Tags that do not already exist
    • Insert/Delete from the EntityTag table
    • Update Entity.TagString
    • Update the Lucene index for the Entity

    Given that the ratio of reads to writes is very big in my application, I think I'm ok with this. The only really time-consuming part is Lucene indexing, because Lucene can only insert and delete from its index, so I have to re-index the entire entity in order to update the TagString. I'm not excited about that, but I think that if I do it in a background thread, it will be fine.

    Time will tell...

    Shawn Simon : cant upmod this post enough
    Funka : the first link in this answer ("SQL server 2005 full text search") no longer seems to work?
    Richard Collette : The updated link would probably be: http://meta.stackoverflow.com/questions/19548/what-search-engine-stackoverflow-is-using
  • Good recap, Winston, thx for following up with your approach.

    From Grant

Saturday, February 12, 2011

How can I reliably discover the full path of the Ruby executable?

I want to write a script, to be packaged into a gem, which will modify its parameters and then exec a new ruby process with the modified params. In other words, something similar to a shell script which modifies its params and then does an exec $SHELL $*. In order to do this, I need a robust way of discovering the path of the ruby executable which is executing the current script. I also need to get the full parameters passed to the current process - both the Ruby parameters and the script arguments.

UPDATE: The Rake source code does it like this:

  RUBY = File.join(Config::CONFIG['bindir'], Config::CONFIG['ruby_install_name']).
    sub(/.*\s.*/m, '"\&"')

But I'll leave this question open in case anyone has an alternative version.

  • If you want to check on linux: read files:

    • /proc/PID/exe
    • /proc/PID/cmdline

    Other useful info can be found in /proc/PID dir

    From VitalieL
  • for the script parameters, of course, use ARGV :) -r

    From rogerdpack

MMORPG Client/Server Coding

How are the UDP and TCP protocols used in MMORPG client/server communication?

For example:

Does the client broadcast (player position, etc) via UDP to the server? or vice versa?

Or is it more like using TCP where the Client requests that the server move the player. The server receives the request, moves the player and sends back to the client that the player is now at position xyz?

The chat channels must be implemented using TCP?

Are there any good articles/books on this? I've found bits and pieces but it seems the real meat and potatoes are won from experience.

  • Half of your question (transport layer protocols used) could be answered by installing wireshark and looking at the traffic.

    From jj33
  • I don't know any details other than observations as a player, but most game most definitely do not wait for a server reply to move a character, that would kill the user experience unless it was turn-based. What looks like happens is the movement is done client-side and sent to the server which then sends those messages to other players. At least in WoW, if a player is lagging you may see them still moving forward then magically appear at another location later, which says to me that the client receives more than location data, but also that they are moving and the direction they were moving and then extrapolates the movement in absence of further data.

    From Davy8
  • Your best bet is probably to take a look at Planeshift's networking code, it's an open source MMO. I believe it's the most developed on the scene(last I checked).

  • A lot of games use UDP for movement related activities--so, like, when you are walking, chances are, a bunch of UDP requests are being sent. The server still ultimately controls whether that's valid, but you don't necessarily care whether every single packet gets to the server. This is why a lot of game clients also use some kind of prediction mechanism.

    In terms of your second mention, yes, it's very common for all control to be managed by the server. You don't want clients to be broadcasting anything to the server; you should do error and input handling server side to prevent people from hacking. You might also limit input per second.

    Anyway, a combination of UDP and TCP would be appropriate--you just need to ask yourself, "Do I want reliability or speed?"

  • There are many different possible implementations, but for the most part, they'll look like this. This pattern is repeated with almost any action in the game world.

    1. The client communicates to the server that the player wants to move.
    2. The client displays the player moving according to what it thinks should happen.
    3. The server validates that the move is something that could happen, given the location of the player.
    4. The server updates the client as to where the player is as far as the server is concerned.
    5. The client updates the players position to reflect the server's worldstate.
  • You may be interested in Project Darkstar. It's an open source MMO framework.

    From Tom Ritter
  • You can't rely on the client to pass in truthful information. Someone will hack the protocol and cheat. Encrypting the data won't stop this - just make it a little harder to do.

    The client should only send in requests for movements etc and the server needs to sanity check the requests to make sure that they don't violate the game rules. The server should only send data back that the client absolutely needs - you can't rely on the client to get a chunk of world data and just filter out everything that the player can't currently observe. Someone will get hold of the extra information and exploit it.

    If the game needs to be 'real-time' then the client needs to assume that the server will allow the movement requests and update the display accordingly - and roll-back the movement if the server corrects it later. Under most conditions the client and server will agree and everything will flow smoothly. They won't agree when the client is attempting to cheat (which is their fault anyway) - or the client is lagging badly due to a poor connection (not much you can do about that).

  • I don't think there's a brief single answer to this question, it's quite wide in its scope. Still, a few points:

    • There's no need to "broadcast" just because you're using UDP. UDP is point-to-point most of the time, in my experience.
    • It's perfectly possible to do your own "secure" communications over UDP, you don't have to use TCP. It's not magical, just ... clever and intricate. :) But for the most part, as you imply, TCP is not suitable for real-time-ish communications in games.
    • There are ways to make TCP more suitable, search for "Nagle algorithm" for instance.
    • You can do chat over UDP, if you've already rolled your own lossless transport protocol on top of it. Many games to this.

    There have been articles about networking in Gamasutra, but I don't have any links handy right now. Not ever sure if they're still openly available, sorry.

    From unwind
  • I think you can learn a lot from reading how others have implemented these types of systems. In that vain, may I point you to the work of Tim Sweeney and The Croquet Consortium

    1. Unrea Networking Architecture
    2. The Croquet Project

    Tim Sweeney's papers transformed the way I thought about programming. I can't recommend them enough.

Best version control system for a non-networked environment?

I am mentoring the programming group of a high school robotics team. I would like to set up a source control repository to avoid the mess of manually copying directories for sharing/backups and merging these by hand. The build location will not usually have network access, so this has led me to distributed version control systems (DVCS), which I am not familiar with.

The largest requirements are the following:

  1. Works in Windows XP and Vista. (absolute must)
  2. Changes can be committed locally. (Seems to be the case with all DVCS's)
  3. Repositories from multiple machines can be merged without network access. (Possibly by storing the repository on a USB drive and swapping the drive to another machine, then merging from there)

It should also be easy to learn and use, preferably through a graphical UI, as I am working with high school students who have never used a version control system.

Any suggestions as to which DVCS fits this the best.

EDIT:

Thanks for the answers. Mercurial looks pretty good, but does it support merging repositories from one directory to another, or do I have to set up a local network to merge across?

  • Git is lovely, but its Windows support is lax in the extreme (even with MSysGit). I would recommend Mercurial. I haven't actually used it myself, but I have heard that its Windows support is quite usable. Also, it has a slightly easier learning curve for people coming from traditional VCS (like SVN).

  • Mercurial is pretty easy to use on both Windows and Linux. TortoiseHg is a gui front end for Windows that integrates into explorer; It works fine. Both are Open Source. It is my understanding that using Git under Windows is less simple.

    Thanks for the answers. Mercurial looks pretty good, but does it support merging repositories from one directory to another, or do I have to set up a local network to merge across?

    Mercurial/TortoiseHg will do this (and more), as will all of the other distributed version control tools (as far as I know). I believe it will solve your problem. It is a DVCS and, with TortoiseHg, it is easy to use on Windows. Other distributed version control tools probably will work too (bzr for example), but I have less experience with them. Subversion (svn) is a centeralized version control tool. With some work-arounds you could get it to function in your environment, but it really does not address the issues you want solved. I have no idea why other responders are suggesting it.

    From ejgottl
  • I found SVN to be amazingly simple to set up and use, especially for a single user!

    One thing that I found really interesting--the ssh+svn protocol used SSH's ability to run a command line on the remote system to actually start SVN, so there was actually NO setup at all on the server outside creating a directory for your repository.

    SVN has a lot of shells if you don't like CLI (TortiseSVN on windows)--so it's as easy to use as anything else.

    From Bill K
  • I guess Mercurial would well fit your needs.

    • It's written in Python, so you won't have any problems running it under Windows.
    • Changes can be easily applied locally using patches or bundles
    • There are a couple of GUI tools available (look for TurtoiseHG)

    Mercurial is the VCS I'm personally using. Really easy to learn. You definitely want to try it over Git since it's support for Windows is way better.

    From skinp
  • I love bazaar: http://bazaar-vcs.org/

    It has all what you ask for and it is very easy to use.

    From Davide
  • Thanks for the answers. Mercurial looks pretty good, but does it support merging repositories from one directory to another, or do I have to set up a local network to merge across?

    Yes it does. All the DVCSes support this. The only difference between this and merging from a server is typically that you pass the appropriate command a local file path instead of a URL.

    In Mercurial it looks like this:

    Assume you have two repositories, one on your hard disk (C:\Project) and one on your flash drive (F:\Project):

    cd C:\Project

    hg pull F:\Project

    Similarly if you have two repositories on the same system:

    cd C:\Project

    hg pull C:\Project1

    If there's a need for a merge, it will create two "heads" and ask you to merge them with hg merge.

    added 1 changesets with 1 changes to 1 files (+1 heads)

    (run 'hg heads' to see heads, 'hg merge' to merge)

    Notice that that's the same as if you pulled and merged from a server.

    From quark

How do you do exponentiation in C?

I tried "x = y ** e", but that didn't work.

  • use the pow function (it takes floats/doubles though).

    man pow:

       #include <math.h>
    
       double pow(double x, double y);
       float powf(float x, float y);
       long double powl(long double x, long double y);
    

    EDIT: BTW, for the special case of positive integer powers of 2, you can use bit shifting: (1 << x) will equal 2 to the power x. There are some potential gotchas with this, but generally it would be correct.

    From Evan Teran
  • To add to what Evan said: C does not have a built-in operator for exponentiation, because it is not a primitive operation for most CPUs. Thus, it's implemented as a library function.

    Also, for computing the function e^x, you can use the exp(double), expf(float), and expl(long double) functions.

    Note that you do not want to use the ^ operator, which is the bitwise exclusive OR operator.

    John Rudy : I'm just learning C, and that ^ threw me for a major loop at first. I'm beginning to "get it" now, but your reminder is very valuable for me and (I'm sure) hundreds more like me. +1!
  • or you could just write the power function, with recursion as a added bonus

    int power(int x, int y){
          if(y == 0)
            return 1;
         return (x * power(x,y-1) );
        }
    

    yes,yes i know this is less effecient space and time complexity but recursion is just more fun!!

    From Mark Lubin
  • pow only works on floating-point numbers (doubles, actually). If you want to take powers of integers, and the base isn't known to be an exponent of 2, you'll have to roll your own.

    Usually the dumb way is good enough.

    int power(int base, unsigned int exp) {
        int i, result = 1;
        for (i = 0; i < exp; i++)
            result *= base;
        return result;
     }
    

    Here's a recursive solution which takes O(log n) space and time instead of the easy O(1) space O(n) time:

    int power(int base, int exp) {
        if (exp == 0)
            return 1;
        else if (exp % 2)
            return base * power(base, exp - 1);
        else {
            int temp = power(base, exp / 2);
            return temp * temp;
        }
    }
    
    Evan Teran : it'll work fine if you cast you int to a double/float and then back to int.
    ephemient : Inefficient, though, and rounding error *will* make a difference when the result gets near INT_MAX.
    From ephemient
  • The non-recursive version of the function is not too hard - here it is for integers:

    long powi(long x, unsigned n)
    {
        long  p;
        long  r;
    
        p = x;
        r = 1.0;
        while (n > 0)
        {
            if (n % 2 == 1)
                r *= p;
            p *= p;
            n /= 2;
        }
    
        return(r);
    }
    

    (Hacked out of code for raising a double value to an integer power - had to remove the code to deal with reciprocals, for example.)

    ephemient : Yes, O(1) space O(log n) time makes this better than the recursive solution, but a little less obvious.