[ quantlib-Bugs-3511954 ] Inconsistent Gray Code usage in Sobol Sequence

[SourceForge.net]

Bugs item #3511954, was opened at 2012-03-27 08:18
Message generated for change (Comment added) made by
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=112740&aid=3511954&group_id=12740

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: None
Group: None
Status: Open
Resolution: None
Priority: 5
Private: No
Submitted By: https://me.yahoo.com/a/Df.Slpks ()
Assigned to: Nobody/Anonymous (nobody)
Summary: Inconsistent Gray Code usage in Sobol Sequence

Initial Comment:
I am referring to the C++ implementation of Sobol low discrepancy sequences in sobolrsg.cpp. The problem I see is also present in the Java port.

SobolRsg::skipTo converts the skip index to a Gray Code, to which it applies the directionIntegers. This looks correct.
SobolRsg::nextInt32Sequence has this comment:
        // instead of using the counter n as new unique generating integer
        // for the n-th draw use the Gray code G(n) as proposed
        // by Antonov and Saleev
However, I do not see the sequenceCounter_ being converted into a Gray Code.

I propose the following change to nextInt32Sequence:

    const std::vector<unsigned long>& SobolRsg::nextInt32Sequence() const
    {
        if (firstDraw_) {
            // it was precomputed in the constructor
            firstDraw_ = false;
            return integerSequence_;
        }
        // increment the counter
        sequenceCounter_++;
        // did we overflow?
     QL_REQUIRE(sequenceCounter_ != 0, "period exceeded");

        // instead of using the counter n as new unique generating integer
        // for the n-th draw use the Gray code G(n) as proposed
        // by Antonov and Saleev
        unsigned long n = sequenceCounter_ ^ (sequenceCounter_ >> 1); // *** LINE CHANGED ***
        // Find rightmost zero bit of n
        int j = 0;
        while (n & 1) { n >>= 1; j++; }
        for (Size k=0; k<dimensionality_; k++) {
            // XOR the appropriate direction number into each component of
            // the integer sequence to obtain a new Sobol integer for that
            // component
            integerSequence_[k] ^= directionIntegers_[k][j];
        }
        return integerSequence_;
    }

Alternately, you could make the use of Gray Codes an option on the algorithm. Of course, I could be mistaken, and only skip needs the Gray Code.

Thank you for providing this library!

Paul Anton Chernoch
Karen Clark and Co.
Boston, MA

----------------------------------------------------------------------

>Comment By: https://me.yahoo.com/a/Df.Slpks ()
Date: 2012-03-27 11:47

Message:
I finished porting the Sobol Sequence code to C#. When I made the change
that I suggested above, it dramatically worsened the results.

Never mind...

Paul

----------------------------------------------------------------------

You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=112740&aid=3511954&group_id=12740

------------------------------------------------------------------------------
This SF email is sponsosred by:
Try Windows Azure free for 90 days Click Here
http://p.sf.net/sfu/sfd2d-msazure
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev