Changeset 11966 for branches

Timestamp:

02/06/15 19:45:12 (10 years ago)

Author:

gkronber

Message:

worked on expression expander for const opt

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization

Files:

• HeuristicLab.Common/ExpressionExtender.cs (modified) (3 diffs)
• Main/Program.cs (modified) (4 diffs)
• Test/TestCanonicalExpressions.cs (modified) (3 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs

@@ -1 +1 @@
 using System;
+using System.CodeDom;
 using System.Collections.Generic;
 using System.Diagnostics;
 using System.Linq;
+using System.Security.Cryptography.X509Certificates;
 using System.Text;
 using System.Threading.Tasks;
@@ -24 +26 @@
     // - transfrom - to + (assumed optimized constants for terms)
 
-
-    // most-recently-used caching (with limited capacity) for canonical representations
-    MostRecentlyUsedCache<string, string> canonicalPhraseCache = new MostRecentlyUsedCache<string, string>(100000);
+    private string sentence;
+    private int syIdx;
+
     public string CanonicalRepresentation(string phrase) {
-      int pos = 0;
-      return CanonicalExpr(phrase, ref pos);
-    }
-
-    private Expr CanonicalExpr(string phrase, ref int pos) {
-      var terms = new List<Term>();
-      terms.Add(CanonicalTerm(phrase, ref pos));
-      var curSy = phrase[pos];
+      InitLex(phrase);
+      var e = CanonicalExpr();
+      return e.ToString();
+    }
+
+
+    private void InitLex(string sentence) {
+      this.sentence = sentence;
+      this.syIdx = 0;
+    }
+
+    private char CurSy() {
+      if (syIdx >= sentence.Length) return '\0';
+      return sentence[syIdx];
+    }
+    private void NewSy() {
+      if (syIdx < sentence.Length) syIdx++;
+    }
+
+    // an expression is a list of terms 
+    // a term is an (ordered) list of factors
+    // a factor is a symbol or an inverted expression
+    // CanonicalExpression reads multiple terms (expressions) and must merge the terms in the expression (ordering and duplicates)
+    // CanonicalTerm reads multiple factors and must expand factors whenever it reads a combined factor (expression) it produces an expression
+    // CanonicalFactor produces an expression 
+
+
+    // canonical expression returns either a single term or a set of terms
+    private Expr CanonicalExpr() {
+      var terms = new List<Expr>();
+      terms.Add(CanonicalTerm());
+      var curSy = CurSy();
       while (curSy == '+' || curSy == '-' || curSy == '^') {
         if (curSy == '+') {
-          pos++;
-          terms.Add(CanonicalTerm(phrase, ref pos));
+          NewSy();
+          terms.Add(CanonicalTerm());
         } else if (curSy == '-') {
-          pos++;
-          terms.Add(CanonicalTerm(phrase, ref pos)); // minus is the same as plus assuming constant opt
+          NewSy();
+          terms.Add(CanonicalTerm()); // minus is the same as plus assuming constant opt
         } else {
-          pos++;
+          NewSy();
           throw new NotImplementedException();
           // var e = Expr(variables, constants);
           // r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
         }
-        curSy = phrase[pos];
-      }
-
-      // at this point we might have multiple constants in the list of terms but we only need one of them
-      var firstConstant = terms.OfType<Variable>().FirstOrDefault(); // if a term is only a variable then it must be a constant (otherwise (for real variables) it would be a product of two constants)
-      if (firstConstant == null) {
-        // no constant found => add a constant offset for each full expression
-        var offset = new Variable();
-        constants.Add(offset);
-        terms.Add(offset);
-      } else {
-        // there is already a constant => remove all others if there are more
-        var otherConsts = terms.OfType<Variable>().Where(t => t != firstConstant).ToArray();
-        foreach (var otherConst in otherConsts) {
-          terms.Remove(otherConst);
-          constants.Remove(otherConst);
-        }
-      }
-      return TermBuilder.Sum(terms);
-    }
-
-    private Term CanonicalTerm(string phrase, ref int pos) {
-      var factors = new List<Factor>();
-      var invFactors = new List<Factor>();
-      var f = CanonicalFact(phrase, ref pos);
+        curSy = CurSy();
+      }
+
+      return new Expr(terms.SelectMany(t => t.Terms));
+    }
+
+    // canonical term returns either a single term (product of factors) or a set of terms 
+    private Expr CanonicalTerm() {
+      var factors = new List<Expr>();
+      var invFactors = new List<Expr>();
+      var f = CanonicalFact();
       if (f != null) factors.Add(f);
-      var curSy = phrase[pos];
+      var curSy = CurSy();
       while (curSy == '*' || curSy == '%') {
         if (curSy == '*') {
-          pos++;
-          f = CanonicalFact(phrase, ref pos); // fact might return string.Empty (for constants)
+          NewSy();
+          f = CanonicalFact();
           if (f != null) factors.Add(f);
         } else {
-          pos++;
-          f = CanonicalFact(phrase, ref pos);
+          NewSy();
+          f = CanonicalFact();
+          f.Invert();
           if (f != null) invFactors.Add(f);
         }
-        curSy = phrase[pos];
-      }
-
-      // cancel factors if they are contained in factors and invFactors
-      foreach (var cancelledF in factors.Intersect(invFactors).ToArray()) {
-        factors.Remove(cancelledF);
-        invFactors.Remove(cancelledF);
-      }
-      // at this point factors and invFactors might be empty
-      if (factors.Count == 0 && invFactors.Count == 0) throw new NotImplementedException();
-
-      if(factors.Count == 1)
-      // extend factors if they are composed of terms
-      // this means that we return a list of terms instead of one single term
-      // at this point factors can only be a list of additive terms
-      var extendedFactors = new List<Factor>();
-
-      // order factors (bysize then lexicographically)
-    }
-
-    private Factor CanonicalFact(string phrase, ref int pos) {
-      var curSy = phrase[pos];
+        curSy = CurSy();
+      }
+
+      // cancellation
+      foreach (var invF in invFactors.ToArray()) {
+        invF.Invert();
+        if (factors.Contains(invF)) {
+          invFactors.Remove(invF);
+          factors.Remove(invF);
+          if (factors.Count == 0) factors.Add(new Expr(new Term('1')));
+        } else invF.Invert();
+      }
+
+      return ExpandFactors(factors, invFactors);
+    }
+
+    private Expr ExpandFactors(List<Expr> factors, List<Expr> invFactors) {
+      // if (invFactors.Count > 0) throw new NotImplementedException();
+      Expr currentFact = factors.First(); // new Expr(simpleFactor));
+      Debug.Assert(!currentFact.Inverse); // the first factor is never an inverted factor
+      foreach (var fact in factors.Skip(1)) {
+        currentFact = AllProducts(currentFact, fact);
+      }
+      foreach (var invF in invFactors) {
+        currentFact = AllInvProducts(currentFact, invF);
+      }
+      return currentFact;
+    }
+
+    private Expr AllProducts(Expr a, Expr b) {
+      var aTerms = a.Terms.ToArray();
+      var bTerms = b.Terms.ToArray();
+      var combs = from aT in aTerms
+                  from bT in bTerms
+                  select new Term(aT.Symbols.Concat(bT.Symbols), aT.InvExpressions.Concat(bT.InvExpressions));
+      return new Expr(combs);
+    }
+
+    private Expr AllInvProducts(Expr a, Expr b) {
+      var aTerms = a.Terms.ToArray();
+      var combs = from aT in aTerms
+                  select new Term(aT.Symbols, aT.InvExpressions.Concat(new Expr[] { b }));
+      return new Expr(combs);
+    }
+
+    // canonical fact returns a factor (either a singe variable, or a set of terms)
+    private Expr CanonicalFact() {
+      var curSy = CurSy();
       if (curSy == '!') {
         throw new NotSupportedException();
       } else if (curSy == '(') {
-        pos++;
-        Expr r = CanonicalExpr(phrase, ref pos);
-        if (phrase[pos] != ')') throw new ArgumentException();
-        pos++;
-        if (r.Kind == ExprKind.SimpleExpr)
-          return new Factor(r.Term);
-        else
-          return new Factor(r.Terms); // a composite factor
+        NewSy();
+        Expr r = CanonicalExpr();
+        if (CurSy() != ')') throw new ArgumentException();
+        NewSy();
+        return r;
       } else if (curSy >= 'a' && curSy <= 'z') {
-        pos++;
-        return new Factor(curSy.ToString());
+        NewSy();
+        return new Expr(new Term(curSy));
         //       } else if (curSy >= '0' && curSy <= '9') {
+      } else if (curSy >= 'A' && curSy <= 'Z') {
+        // treat nonterminals in the same way as variables
+        NewSy();
+        return new Expr(new Term(curSy));
+
       } else throw new ArgumentException("found symbol " + curSy);
     }
 
-    #region factor
-    private enum FactorKind { SimpleFactor, Expr }
-    private class Factor {
-      public readonly FactorKind Kind;
-      public readonly string Value; // only set for Kind == SimpleFactor
-      public readonly IEnumerable<string> Values; // only set for Kind == Expr 
-
-      public Factor(string f) {
-        this.Kind = FactorKind.SimpleFactor;
-        this.Value = f;
-      }
-      public Factor(IEnumerable<string> factorTerms) {
-        this.Kind = FactorKind.Expr;
-        this.Values = factorTerms;
+    #region term
+    // term can be merged (essentially an ordered list of factors)
+    internal class Term : IComparable<Term> {
+      private readonly SortedList<char, int> factorSymbs; // factor symbol and the number of occurrences
+      private readonly SortedList<Expr, int> invExpressions;
+
+      public IEnumerable<char> Symbols {
+        get {
+          return factorSymbs.SelectMany(p => Enumerable.Repeat(p.Key, p.Value));
+        }
+      }
+
+      public IEnumerable<Expr> InvExpressions {
+        get {
+          if (invExpressions == null) return Enumerable.Empty<Expr>();
+          return invExpressions.Where(p => p.Value > 0).SelectMany(p => Enumerable.Repeat(p.Key, p.Value));
+        }
+      }
+
+      public Term(char f) {
+        factorSymbs = new SortedList<char, int>(new FactorComparer());
+        factorSymbs.Add(f, 1);
+      }
+      public Term(IEnumerable<char> factors, IEnumerable<Expr> invFactors) {
+        factorSymbs = new SortedList<char, int>(new FactorComparer());
+        invExpressions = new SortedList<Expr, int>();
+        foreach (var f in factors) {
+          if (factorSymbs.ContainsKey(f)) factorSymbs[f] += 1;
+          else factorSymbs.Add(f, 1);
+        }
+
+        foreach (var invF in invFactors) {
+          if (invF.Terms.Count == 1) {
+            var t = invF.Terms.First();
+            foreach (var f in factors.Concat(new char[] { '1' })) {
+              if (t.factorSymbs.ContainsKey(f)) {
+                t.factorSymbs[f] -= 1;
+                if (t.factorSymbs[f] == 0) t.factorSymbs.Remove(f);
+              }
+            }
+          }
+          if (invExpressions.ContainsKey(invF)) invExpressions[invF] += 1;
+          else invExpressions.Add(invF, 1);
+        }
+      }
+
+      public int CompareTo(Term other) {
+        if (ContainsNonTerminal(Symbols) && !ContainsNonTerminal(other.Symbols)) {
+          return 1;
+        } else if (!ContainsNonTerminal(Symbols) && ContainsNonTerminal(other.Symbols)) {
+          return -1;
+        } else {
+          var countComp = Symbols.Count().CompareTo(other.Symbols.Count());
+          if (countComp != 0) return countComp;
+          return string.Join("", Symbols).CompareTo(string.Join("", other.Symbols));
+        }
       }
 
       public override string ToString() {
-        if (Kind == FactorKind.SimpleFactor) return Value;
-        else return string.Join("+", Values);
-      }
-      public override bool Equals(object obj) {
-        var other = obj as Factor;
-        if (other == null) return false;
-        if (other.Kind != this.Kind) return false;
-        if (Kind == FactorKind.SimpleFactor) return this.Value == other.Value;
-        if (this.Values.Count() != other.Values.Count()) return false;
-        if (this.Values.Zip(other.Values, Tuple.Create).All(t => t.Item1 == t.Item2)) return true;
-        return false;
-      }
-      public override int GetHashCode() {
-        var h = 31415;
-        if (Value != null) h ^= Value.GetHashCode();
-        foreach (var v in Values) {
-          h ^= v.GetHashCode();
-        }
-        return h;
-      }
-    }
-    #endregion
-    #region term
-    private enum TermKind { SimpleTerm, Term }
-    private class Term {
-      public readonly TermKind Kind;
-      public readonly Factor Factor; // only set for Kind == Simple
-      public readonly IEnumerable<Factor> Factors;
-
-      public Term(Factor f) {
-        this.Kind = TermKind.SimpleTerm;
-        this.Factor = f;
-      }
-      public Term(IEnumerable<Factor> factors) {
-        this.Kind = TermKind.Term;
-        this.Factors = factors;
-      }
-
-      public override string ToString() {
-        if (Kind == TermKind.SimpleTerm) return Factor.ToString();
-        else return string.Join("+", Factors);
+        if (InvExpressions.Any())
+          return string.Join("*", Symbols) + "%" + string.Join("%", InvExpressions);
+        else {
+          return string.Join("*", Symbols);
+        }
       }
       public override bool Equals(object obj) {
         var other = obj as Term;
         if (other == null) return false;
-        if (other.Kind != this.Kind) return false;
-        if (Kind == TermKind.SimpleTerm) return this.Factor == other.Factor;
-        if (this.Factors.Count() != other.Factors.Count()) return false;
-        if (this.Factors.Zip(other.Factors, Tuple.Create).All(t => t.Item1 == t.Item2)) return true;
-        return false;
+        if (this.Symbols.Count() != other.Symbols.Count()) return false;
+        if (this.InvExpressions.Count() != other.InvExpressions.Count()) return false;
+        if (this.Symbols.Zip(other.Symbols, Tuple.Create).Any(t => t.Item1 != t.Item2)) return false;
+        if (this.InvExpressions.Zip(other.InvExpressions, Tuple.Create).Any(t => t.Item1 != t.Item2)) return false;
+        return true;
       }
       public override int GetHashCode() {
         var h = 31415;
-        if (Factor != null) h ^= Factor.GetHashCode();
-        foreach (var t in Factors) {
-          h ^= t.GetHashCode();
+        foreach (var v in Symbols) {
+          h ^= v.GetHashCode();
+        }
+        foreach (var v in InvExpressions) {
+          h ^= v.GetHashCode();
         }
         return h;
@@ -204 +253 @@
     }
     #endregion
+
     #region expr
-    private enum ExprKind { SimpleExpr, Expr }
-    private class Expr {
-      public readonly ExprKind Kind;
-      public readonly string Term; // only set for Kind == SimpleExpr
-      public readonly IEnumerable<string> Terms; // only set for Kind == Expr 
-
-      public Expr(string f) {
-        this.Kind = ExprKind.SimpleExpr;
-        this.Term = f;
-      }
-      public Expr(IEnumerable<string> exprTerms) {
-        this.Kind = ExprKind.Expr;
-        this.Terms = exprTerms;
+
+    internal class Expr : IComparable<Expr> {
+      public readonly SortedSet<Term> Terms; // only set for Kind == Expr 
+      public bool Inverse;
+      public Expr(Term t) {
+        Terms = new SortedSet<Term>();
+        Terms.Add(t);
+      }
+      public Expr(IEnumerable<Term> exprTerms) {
+        Terms = new SortedSet<Term>();
+        foreach (var t in exprTerms) {
+          Terms.Add(t);
+        }
+      }
+
+      public void Merge(Expr other) {
+        this.Terms.UnionWith(other.Terms);
+      }
+
+      public int CompareTo(Expr other) {
+        var sizeComp = this.Terms.Count.CompareTo(other.Terms.Count);
+        if (sizeComp != 0) return sizeComp;
+        // same size => compare terms
+        foreach (var pair in Terms.Zip(other.Terms, Tuple.Create)) {
+          var termComp = pair.Item1.CompareTo(pair.Item2);
+          if (termComp != 0) return termComp;
+        }
+        return 0;
       }
 
       public override string ToString() {
-        if (Kind == ExprKind.SimpleExpr) return Term;
-        else return string.Join("+", Terms);
+        if (Inverse && Terms.Count > 1)
+          return "(" + string.Join("+", Terms) + ")";
+        else if (Inverse && Terms.Count == 1) {
+          return Terms.First().ToString().Replace("%", "#").Replace("*", "%").Replace("#", "*");
+        } else
+          return string.Join("+", Terms);
       }
       public override bool Equals(object obj) {
         var other = obj as Expr;
         if (other == null) return false;
-        if (other.Kind != this.Kind) return false;
-        if (Kind == ExprKind.SimpleExpr) return this.Term == other.Term;
+        if (this.Inverse != other.Inverse) return false;
         if (this.Terms.Count() != other.Terms.Count()) return false;
-        if (this.Terms.Zip(other.Terms, Tuple.Create).All(t => t.Item1 == t.Item2)) return true;
-        return false;
+        return this.Terms.Intersect(other.Terms).Count() == this.Terms.Count;
       }
       public override int GetHashCode() {
         var h = 31415;
-        if (Term != null) h ^= Term.GetHashCode();
-        foreach (var t in Terms) {
-          h ^= t.GetHashCode();
-        }
+        if (Terms != null)
+          foreach (var t in Terms) {
+            h ^= t.GetHashCode();
+          }
         return h;
       }
+
+      public void Invert() {
+        this.Inverse = !Inverse;
+      }
     }
     #endregion
-    // private enum TermKind { }
-    // private class Term {
-    //   public TermKind Kind;
-    //   public string FirstFactor; // always set
-    //   public IEnumerable<string> RemainingFactors; // only set for Kind == Expr 
-    // }
-
-    // cache the canonical form of terms for performance reasons
-    private Dictionary<string, string> canonicalTermDictionary = new Dictionary<string, string>();
-    private string CanonicalTerm(string term) {
-      string canonicalTerm;
-      if (!canonicalTermDictionary.TryGetValue(term, out canonicalTerm)) {
-        // add
-        var chars = term.ToCharArray();
-        Array.Sort(chars);
-        var sb = new StringBuilder(chars.Length);
-        // we want to have the up-case characters last
-        for (int i = chars.Length - 1; i > 0; i--) {
-          if (chars[i] != '*') {
-            sb.Append(chars[i]);
-            if (chars[i - 1] != '*') sb.Append('*');
-          }
-        }
-        if (chars[0] != '*') sb.Append(chars[0]); // last term
-        canonicalTerm = sb.ToString();
-        canonicalTermDictionary.Add(term, canonicalTerm);
-      }
-      return canonicalTerm;
+    internal static bool IsNonTerminal(char symb) {
+      return symb >= 'A' && symb <= 'Z';
+    }
+    internal static bool ContainsNonTerminal(IEnumerable<char> symbs) {
+      return symbs.Any(IsNonTerminal);
+    }
+
+    internal class FactorComparer : IComparer<char> {
+      public int Compare(char x, char y) {
+        if (IsNonTerminal(x) && !IsNonTerminal(y)) {
+          return 1;
+        } else if (!IsNonTerminal(x) && IsNonTerminal(y)) {
+          return -1;
+        } else if (IsNonTerminal(x) && IsNonTerminal(y)) {
+          return x.CompareTo(y);
+        } else {
+          return x.CompareTo(y);
+        }
+      }
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs

@@ -27 +27 @@
 
       //RunDemo();
-      RunGpDemo();
-      // RunGridTest();
+      // RunGpDemo();
+      RunGridTest();
       //RunGpGridTest();
     }
 
     private static void RunGridTest() {
-      int maxIterations = 70000; // for poly-10 with 50000 evaluations no successful try with hl yet
+      int maxIterations = 200000; // for poly-10 with 50000 evaluations no successful try with hl yet
       //var globalRandom = new Random(31415);
       var localRandSeed = 31415;
-      var reps = 30;
+      var reps = 20;
 
       var policyFactories = new Func<IBanditPolicy>[]
@@ -112 +112 @@
       var instanceFactories = new Func<Random, Tuple<IProblem, int>>[]
       {
-        //(rand) => Tuple.Create((IProblem)new SantaFeAntProblem(), 17),
+        (rand) => Tuple.Create((IProblem)new SantaFeAntProblem(), 17),
         //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:false ), 15),
         //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:true ), 15),
@@ -121 +121 @@
 
       foreach (var instanceFactory in instanceFactories) {
-        foreach (var useCanonical in new bool[] { true /*, false */}) {
-          foreach (var randomTries in new int[] { 0 /*, 1, 10 /*, /* 5, 100 /*, 500, 1000 */}) {
+        foreach (var useCanonical in new bool[] { true, false }) {
+          foreach (var randomTries in new int[] { 0, 1, 10 /*, /* 5, 100 /*, 500, 1000 */}) {
             foreach (var policyFactory in policyFactories) {
               var myRandomTries = randomTries;
@@ -146 +146 @@
                 var problem = instance.Item1;
                 var maxLen = instance.Item2;
-                //var alg = new SequentialSearch(problem, maxLen, myLocalRand, myRandomTries,
-                //  new GenericGrammarPolicy(problem, policyFactory(), useCanonical));
-                var alg = new SequentialSearch(problem, maxLen, myLocalRand,
-                  myRandomTries,
-                  new GenericFunctionApproximationGrammarPolicy(problem,
-                    useCanonical));
+                var alg = new SequentialSearch(problem, maxLen, myLocalRand, myRandomTries,
+                  new GenericGrammarPolicy(problem, policyFactory(), useCanonical));
+                // var alg = new SequentialSearch(problem, maxLen, myLocalRand,
+                //   myRandomTries,
+                //   new GenericFunctionApproximationGrammarPolicy(problem,
+                //     useCanonical));
                 //var alg = new ExhaustiveBreadthFirstSearch(problem, 25);
                 //var alg = new AlternativesContextSampler(problem, 25);

branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestCanonicalExpressions.cs

@@ -62 +62 @@
 
       // when using constant opt the negative sign is not necessary because a negative factor can be produced
-      Assert.AreEqual("a*b+c*b", extender.CanonicalRepresentation("b*(c-a)"));
+      Assert.AreEqual("a*b+b*c", extender.CanonicalRepresentation("b*(c-a)"));
       Assert.AreEqual("a*b+a*d+b*c+c*d", extender.CanonicalRepresentation("(b-d)*(c-a)"));
     }
@@ -74 +74 @@
 
       Assert.AreEqual("a*b%(a+b)%(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)"));
-      Assert.AreEqual("a*b%(c+d)%(a%e+b%e)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
+      Assert.AreEqual("a*b%(a%e+b%e)%(c+d)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
       // a*b*e%(c+d)%(a+b)
     }
@@ -80 +80 @@
     public void TestDivisionCancellation() {
       var extender = new ExpressionExtender();
-      Assert.AreEqual("a", extender.CanonicalRepresentation("a%a"));
-      Assert.AreEqual("a*a", extender.CanonicalRepresentation("a*a%a"));
-      Assert.AreEqual("1%a", extender.CanonicalRepresentation("(a%a)%a"));
+      Assert.AreEqual("1", extender.CanonicalRepresentation("a%a"));
+      Assert.AreEqual("a", extender.CanonicalRepresentation("a*a%a"));
+      Assert.AreEqual("1%a", extender.CanonicalRepresentation("(a%a)%a")); 
       Assert.AreEqual("1%a", extender.CanonicalRepresentation("a%a%a"));
       Assert.AreEqual("a", extender.CanonicalRepresentation("a%(a%a)"));
+      Assert.AreEqual("1", extender.CanonicalRepresentation("(a+b)%(b+a)"));
+      Assert.AreEqual("1%a+1%b", extender.CanonicalRepresentation("(a+b)%(a*b)"));
     }
   }